C++ 實現(xiàn)求小于n的最大素數(shù)的實例

創(chuàng)新互聯(lián)服務(wù)項目包括從江網(wǎng)站建設(shè)、從江網(wǎng)站制作、從江網(wǎng)頁制作以及從江網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，從江網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到從江省份的部分城市，未來相信會繼續(xù)擴大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

枚舉就是基于已有知識鏡像答案猜測的一種問題求解策略

問題：求小于n的最大素數(shù)

分析：

    找不到一個數(shù)學公式，使得根據(jù)N就可以計算出這個素數(shù)    

    我們思考：

    N-1是素數(shù)么？N-2是素數(shù)嗎？...    
    所以我們就是判斷N-K是否為素數(shù)：
    N-K是素數(shù)的充分必要條件：N-K不能被[2,n-k)中任何一個整除    
    判斷N-K是否為素數(shù)的問題可以轉(zhuǎn)化為：
    求小于N-K的全部素數(shù)（求“小于N的最大素數(shù)”中的條件是“n不能被[2,n)中任意一個素數(shù)整除”，而不是整數(shù)）
    不能被[2,n)中任意一個素數(shù)整除的數(shù)一定是素數(shù)，因為那些整數(shù)都是以素數(shù)為因子的，
    所以沒必要檢測所有整數(shù)，檢測所有素數(shù)就ok了   

解決方法：

    2是素數(shù)，記為PRIM 0

    根據(jù)PRIM 0，PRIM 1，...PRIM K，尋找比PRIM K大的最小素數(shù)PRIM K+1（這里是根據(jù)素數(shù)找素數(shù)）

    如果PRIM K+1大于N，則PRIM K是我們需要找的素數(shù)，否則繼續(xù)尋找    

    枚舉：

        從可能的集合中一一列舉各元素
        根據(jù)所知道的知識，給一個猜測的答案
        比如：2是素數(shù)，那2是本問題的解么    

    枚舉算法：

        對問題可能解集合的每一項：
            根據(jù)問題給定的檢驗條件判斷哪些是成立的
            使條件成立的即為問題的解    

    枚舉過程：

        判斷猜測答案是否正確
            2是小于N的最大素數(shù)么？
        進行新的猜測：

            有兩個關(guān)鍵因素要注意：

                1. 猜測的結(jié)果必須是前面的猜測中沒有出現(xiàn)過的。每次猜測的素數(shù)一定要比已經(jīng)找到的素數(shù)大
                2. 猜測的過程中要及早排除錯誤的答案。比如：除2之外，只有奇數(shù)才可能是素數(shù)

    枚舉過程中需要考慮的問題：

        1. 給出解空間，建立簡介的數(shù)學模型
            可能的情況是什么？
            模型中變量數(shù)盡可能的少（使規(guī)模盡量小），他們之間相互獨立
                求“小于N的最大素數(shù)”中的條件是“n不能被[2,n)中任意一個素數(shù)整除”
                而不是“n不能被[2,n)中任意一個整數(shù)整除”

        2. 減少搜索的空間

            利用知識縮小模型中各變量的取值范圍，避免不必要的計算
            比如：較少代碼中循環(huán)體執(zhí)行的次數(shù)
                除2之外，只有奇數(shù)才可能是素數(shù)，{2,2*i+1|1<=i,2*i+1

        3. 采用合適的搜索順序

            搜索空間的遍歷順序要與模型中條件表達式一致
            例如：對{2,2*i+1|1<=i,2*i+1

    枚舉關(guān)鍵字（枚舉核心）：

        減少規(guī)模

實例代碼：

#include 
using namespace std;
int prim[50000];//用來存所有素數(shù) 
int primNum=0;//用來記錄 prim數(shù)組中已經(jīng)存入的素數(shù)的數(shù)量 
int times=0; //用于記錄求解問題的總共判斷次數(shù) 
int primLessN(int n);
int primLessN_2(int n);
bool isPrimMothed(int n); //判斷一個數(shù)是否為素數(shù) 

/*
  方法一：由前往后用素數(shù)判斷的枚舉法：
  求“小于N的最大素數(shù)”中的條件是“n不能被[2,n)中任意一個素數(shù)整除”，而不是整數(shù)
   
  當n=10 0000時，
  ans=99991
  times=4626 4478次 
  primNum=9592 
  
  我每一個素數(shù)被判斷出來，都要遍歷一下之前的素數(shù)表
  而判斷10 0000的時候，外層循環(huán)走了50000，里層每一個素數(shù)就是一次之前素數(shù)表的遍歷
  50000*（1+2+3+...+9592)=50000* 4600 8082
  前面那個數(shù)沒有50000，還要減去那些非素數(shù) 
  從 50000* 4600 8082可以看出，主要是之前那些素數(shù)花的時間，非素數(shù)幾乎沒花時間
  非素數(shù)= 4626 4478-4600 8082= 25 6450 
  只有25萬，雖然還是要比下面多很多，因為是從前往后比較的 
*/
int primLessN(int n)
{
  prim[0]=2; //2是最小的素數(shù)
  primNum++; 
  for(int i=3;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<

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！