好的程序員不管是C語言，還是PHP程序都能熟悉的掌握，今天這篇文章是武林技術頻道小編為大家帶來的C++ 實現求小于n的最大素數的實例，一起跟著武林技術頻道小編的步伐來學習吧！
C++ 實現求小于n的最大素數的實例
枚舉就是基于已有知識鏡像答案猜測的一種問題求解策略
問題：求小于n的最大素數
分析：
??? 找不到一個數學公式，使得根據N就可以計算出這個素數????
??? 我們思考：
??? N-1是素數么？N-2是素數嗎？...????
??? 所以我們就是判斷N-K是否為素數：
??? N-K是素數的充分必要條件：N-K不能被[2,n-k)中任何一個整除????
??? 判斷N-K是否為素數的問題可以轉化為：
??? 求小于N-K的全部素數（求“小于N的最大素數”中的條件是“n不能被[2,n)中任意一個素數整除”，而不是整數）
??? 不能被[2,n)中任意一個素數整除的數一定是素數，因為那些整數都是以素數為因子的，
??? 所以沒必要檢測所有整數，檢測所有素數就ok了???
解決方法：
??? 2是素數，記為PRIM 0
??? 根據PRIM 0，PRIM 1，...PRIM K，尋找比PRIM K大的最小素數PRIM K+1（這里是根據素數找素數）
??? 如果PRIM K+1大于N，則PRIM K是我們需要找的素數，否則繼續尋找????
??? 枚舉：
??????? 從可能的集合中一一列舉各元素
??????? 根據所知道的知識，給一個猜測的答案
??????? 比如：2是素數，那2是本問題的解么????
??? 枚舉算法：
??????? 對問題可能解集合的每一項：
??????????? 根據問題給定的檢驗條件判斷哪些是成立的
??????????? 使條件成立的即為問題的解????
??? 枚舉過程：
??????? 判斷猜測答案是否正確
??????????? 2是小于N的最大素數么？
??????? 進行新的猜測：
??????????? 有兩個關鍵因素要注意：
??????????????? 1. 猜測的結果必須是前面的猜測中沒有出現過的。每次猜測的素數一定要比已經找到的素數大
??????????????? 2. 猜測的過程中要及早排除錯誤的答案。比如：除2之外，只有奇數才可能是素數
??? 枚舉過程中需要考慮的問題：
??????? 1. 給出解空間，建立簡介的數學模型
??????????? 可能的情況是什么？
??????????? 模型中變量數盡可能的少（使規模盡量小），他們之間相互獨立
??????????????? 求“小于N的最大素數”中的條件是“n不能被[2,n)中任意一個素數整除”
??????????????? 而不是“n不能被[2,n)中任意一個整數整除”
??????? 2. 減少搜索的空間
??????????? 利用知識縮小模型中各變量的取值范圍，避免不必要的計算
??????????? 比如：較少代碼中循環體執行的次數
??????????????? 除2之外，只有奇數才可能是素數，{2,2*i+1|1<=i,2*i+1<n}
??????? 3. 采用合適的搜索順序
??????????? 搜索空間的遍歷順序要與模型中條件表達式一致
??????????? 例如：對{2,2*i+1|1<=i,2*i+1<n}，按照從小到大的順序???????????
??? 枚舉關鍵字（枚舉核心）：
??????? 減少規模
實例代碼：
#include <iostream>using namespace std;int prim[50000];//用來存所有素數 int primNum=0;//用來記錄 prim數組中已經存入的素數的數量 int times=0; //用于記錄求解問題的總共判斷次數 int primLessN(int n);int primLessN_2(int n);bool isPrimMothed(int n); //判斷一個數是否為素數 /* 方法一：由前往后用素數判斷的枚舉法： 求“小于N的最大素數”中的條件是“n不能被[2,n)中任意一個素數整除”，而不是整數 當n=10 0000時， ans=99991 times=4626 4478次 primNum=9592 我每一個素數被判斷出來，都要遍歷一下之前的素數表 而判斷10 0000的時候，外層循環走了50000，里層每一個素數就是一次之前素數表的遍歷 50000*（1+2+3+...+9592)=50000* 4600 8082 前面那個數沒有50000，還要減去那些非素數 從 50000* 4600 8082可以看出，主要是之前那些素數花的時間，非素數幾乎沒花時間 非素數= 4626 4478-4600 8082= 25 6450 只有25萬，雖然還是要比下面多很多，因為是從前往后比較的 */int primLessN(int n){ prim[0]=2; //2是最小的素數 primNum++; for(int i=3;i<n;i+=2){ bool isPrim=1; //isPrim用來判斷一個數是否為素數 for(int j=0;j<primNum;j++){ times++; if(i%prim[j]==0){ isPrim=0; break; //沒加break之前， 當n=10 0000時，times=2 5239 6936次 （2.5億） ，加了之后times=4626 4478次 （4.5千萬次） } } if(isPrim) prim[primNum++]=i;//如果是素數，則存入prim素數數組 } return prim[primNum-1];} /* 方法二： 由后往前的整數枚舉法 而且方法二的空間消耗也少 當n=10 0000時， ans=99991 times=346次 當n=100 0000時，用方法一的話，根本算不出來 ans=99 9983 times=1811次 當n=1 0000 0000(一億)時， ans=9999 9989 times=11314次 當n=10 0000 0000(十億)時， ans=9 9999 9937 times=52537次 */bool isPrimMothed(int n){ bool isPrim=1; //isPrim用來判斷一個數是否為素數 if(n==2||n==3) return 1; for(int i=2;i*i<=n;i++){ times++; if(n%i==0) return 0; } return 1;} int primLessN_2(int n){ for(int i=n;i>=2;i--){ if(isPrimMothed(i)) return i; } }int main(){ int n; scanf("%d",&n); //int ans=primLessN(n); int ans=primLessN_2(n); cout<<ans<<endl; printf("總判斷次數times:%d/n",times); printf("總素數數primNum:%d/n",primNum); return 0;}以上這些是武林技術頻道小編給大家介紹的C++ 實現求小于n的最大素數的實例，閱讀了這篇文章，大家是否對C++有所了解了?希望大家繼續支持武林技術頻道。新聞熱點
疑難解答
圖片精選
