C++ 實(shí)現(xiàn)求小于n的最大素?cái)?shù)的實(shí)例
枚舉就是基于已有知識(shí)鏡像答案猜測的一種問題求解策略
問題：求小于n的最大素?cái)?shù)
分析：
找不到一個(gè)數(shù)學(xué)公式，使得根據(jù)N就可以計(jì)算出這個(gè)素?cái)?shù)
我們思考：
N-1是素?cái)?shù)么？N-2是素?cái)?shù)嗎？...
所以我們就是判斷N-K是否為素?cái)?shù)：
N-K是素?cái)?shù)的充分必要條件：N-K不能被[2,n-k)中任何一個(gè)整除
判斷N-K是否為素?cái)?shù)的問題可以轉(zhuǎn)化為：
求小于N-K的全部素?cái)?shù)（求“小于N的最大素?cái)?shù)”中的條件是“n不能被[2,n)中任意一個(gè)素?cái)?shù)整除”，而不是整數(shù)）
不能被[2,n)中任意一個(gè)素?cái)?shù)整除的數(shù)一定是素?cái)?shù)，因?yàn)槟切┱麛?shù)都是以素?cái)?shù)為因子的，
所以沒必要檢測所有整數(shù)，檢測所有素?cái)?shù)就ok了
解決方法：
2是素?cái)?shù)，記為PRIM 0
根據(jù)PRIM 0，PRIM 1，...PRIM K，尋找比PRIM K大的最小素?cái)?shù)PRIM K+1（這里是根據(jù)素?cái)?shù)找素?cái)?shù)）
如果PRIM K+1大于N，則PRIM K是我們需要找的素?cái)?shù)，否則繼續(xù)尋找
枚舉：
從可能的集合中一一列舉各元素
根據(jù)所知道的知識(shí)，給一個(gè)猜測的答案
比如：2是素?cái)?shù)，那2是本問題的解么
枚舉算法：
對(duì)問題可能解集合的每一項(xiàng)：
根據(jù)問題給定的檢驗(yàn)條件判斷哪些是成立的
使條件成立的即為問題的解
枚舉過程：
判斷猜測答案是否正確
2是小于N的最大素?cái)?shù)么？
進(jìn)行新的猜測：
有兩個(gè)關(guān)鍵因素要注意：
1. 猜測的結(jié)果必須是前面的猜測中沒有出現(xiàn)過的。每次猜測的素?cái)?shù)一定要比已經(jīng)找到的素?cái)?shù)大
2. 猜測的過程中要及早排除錯(cuò)誤的答案。比如：除2之外，只有奇數(shù)才可能是素?cái)?shù)
枚舉過程中需要考慮的問題：
1. 給出解空間，建立簡介的數(shù)學(xué)模型
可能的情況是什么？
模型中變量數(shù)盡可能的少（使規(guī)模盡量小），他們之間相互獨(dú)立
求“小于N的最大素?cái)?shù)”中的條件是“n不能被[2,n)中任意一個(gè)素?cái)?shù)整除”
而不是“n不能被[2,n)中任意一個(gè)整數(shù)整除”
2. 減少搜索的空間
利用知識(shí)縮小模型中各變量的取值范圍，避免不必要的計(jì)算
比如：較少代碼中循環(huán)體執(zhí)行的次數(shù)
除2之外，只有奇數(shù)才可能是素?cái)?shù)，{2,2*i+1|1<=i,2*i+1<n}
3. 采用合適的搜索順序
搜索空間的遍歷順序要與模型中條件表達(dá)式一致
例如：對(duì){2,2*i+1|1<=i,2*i+1<n}，按照從小到大的順序
枚舉關(guān)鍵字（枚舉核心）：
減少規(guī)模
實(shí)例代碼：
#include <iostream>using namespace std;int prim[50000];//用來存所有素?cái)?shù) int primNum=0;//用來記錄 prim數(shù)組中已經(jīng)存入的素?cái)?shù)的數(shù)量 int times=0; //用于記錄求解問題的總共判斷次數(shù) int primLessN(int n);int primLessN_2(int n);bool isPrimMothed(int n); //判斷一個(gè)數(shù)是否為素?cái)?shù) /* 方法一：由前往后用素?cái)?shù)判斷的枚舉法： 求“小于N的最大素?cái)?shù)”中的條件是“n不能被[2,n)中任意一個(gè)素?cái)?shù)整除”，而不是整數(shù) 當(dāng)n=10 0000時(shí)， ans=99991 times=4626 4478次 primNum=9592 我每一個(gè)素?cái)?shù)被判斷出來，都要遍歷一下之前的素?cái)?shù)表 而判斷10 0000的時(shí)候，外層循環(huán)走了50000，里層每一個(gè)素?cái)?shù)就是一次之前素?cái)?shù)表的遍歷 50000*（1+2+3+...+9592)=50000* 4600 8082 前面那個(gè)數(shù)沒有50000，還要減去那些非素?cái)?shù) 從 50000* 4600 8082可以看出，主要是之前那些素?cái)?shù)花的時(shí)間，非素?cái)?shù)幾乎沒花時(shí)間 非素?cái)?shù)= 4626 4478-4600 8082= 25 6450 只有25萬，雖然還是要比下面多很多，因?yàn)槭菑那巴蟊容^的 */int primLessN(int n){ prim[0]=2; //2是最小的素?cái)?shù) primNum++; for(int i=3;i<n;i+=2){ bool isPrim=1; //isPrim用來判斷一個(gè)數(shù)是否為素?cái)?shù) for(int j=0;j<primNum;j++){ times++; if(i%prim[j]==0){ isPrim=0; break; //沒加break之前， 當(dāng)n=10 0000時(shí)，times=2 5239 6936次 （2.5億） ，加了之后times=4626 4478次 （4.5千萬次） } } if(isPrim) prim[primNum++]=i;//如果是素?cái)?shù)，則存入prim素?cái)?shù)數(shù)組 } return prim[primNum-1];} /* 方法二： 由后往前的整數(shù)枚舉法 而且方法二的空間消耗也少 當(dāng)n=10 0000時(shí)， ans=99991 times=346次 當(dāng)n=100 0000時(shí)，用方法一的話，根本算不出來 ans=99 9983 times=1811次 當(dāng)n=1 0000 0000(一億)時(shí)， ans=9999 9989 times=11314次 當(dāng)n=10 0000 0000(十億)時(shí)， ans=9 9999 9937 times=52537次 */bool isPrimMothed(int n){ bool isPrim=1; //isPrim用來判斷一個(gè)數(shù)是否為素?cái)?shù) 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("總判斷次數(shù)times:%d/n",times); printf("總素?cái)?shù)數(shù)primNum:%d/n",primNum); return 0;}感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
新聞熱點(diǎn)
疑難解答
