溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
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;
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
