C++實(shí)現(xiàn)求小于n的最大素?cái)?shù)的實(shí)例

C++ 實(shí)現(xiàn)求小于n的最大素?cái)?shù)的實(shí)例

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

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

問題：求小于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ù)為因子的，
    所以沒必要檢測(cè)所有整數(shù)，檢測(cè)所有素?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è)猜測(cè)的答案
        比如：2是素?cái)?shù)，那2是本問題的解么

枚舉算法：

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

枚舉過程：

        判斷猜測(cè)答案是否正確
            2是小于N的最大素?cái)?shù)么？
        進(jìn)行新的猜測(cè)：

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

1. 猜測(cè)的結(jié)果必須是前面的猜測(cè)中沒有出現(xiàn)過的。每次猜測(cè)的素?cái)?shù)一定要比已經(jīng)找到的素?cái)?shù)大
2. 猜測(cè)的過程中要及早排除錯(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ì)本站的支持！

文章標(biāo)題：C++實(shí)現(xiàn)求小于n的最大素?cái)?shù)的實(shí)例
本文地址：http://chinadenli.net/article4/gigcoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、虛擬主機(jī)、網(wǎng)站設(shè)計(jì)、靜態(tài)網(wǎng)站、App設(shè)計(jì)、企業(yè)建站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区

C++實(shí)現(xiàn)求小于n的最大素?cái)?shù)的實(shí)例