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;}感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
圖片精選
