C++ 實現(xiàn)求小于n的最大素數(shù)的實例
C++ 實現(xiàn)求小于n的最大素數(shù)的實例
枚舉就是基于已有知識鏡像答案猜測的一種問題求解策略
問題:求小于n的最大素數(shù)
分析:
找不到一個數(shù)學(xué)公式,使得根據(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ù)學(xué)模型
可能的情況是什么?
模型中變量數(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<n}
3. 采用合適的搜索順序
搜索空間的遍歷順序要與模型中條件表達式一致
例如:對{2,2*i+1|1<=i,2*i+1<n},按照從小到大的順序
枚舉關(guān)鍵字(枚舉核心):
減少規(guī)模
實例代碼:
#include <iostream> 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<n;i+=2){ bool isPrim=1; //isPrim用來判斷一個數(shù)是否為素數(shù) 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;//如果是素數(shù),則存入prim素數(shù)數(shù)組 } return prim[primNum-1]; } /* 方法二: 由后往前的整數(shù)枚舉法 而且方法二的空間消耗也少 當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用來判斷一個數(shù)是否為素數(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("總素數(shù)數(shù)primNum:%d\n",primNum); return 0; }
感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!
相關(guān)文章
C++入門基礎(chǔ)之命名空間、輸入輸出和缺省參數(shù)
C++入門基礎(chǔ)篇的內(nèi)容為C++的基本特性,只有在掌握C++的基本特性后,是進入后面類和對象學(xué)習的基礎(chǔ),下面這篇文章主要給大家介紹了關(guān)于C++入門基礎(chǔ)之命名空間、輸入輸出和缺省參數(shù)的相關(guān)資料,需要的朋友可以參考下2023-01-01C++?Boost?CircularBuffer算法超詳細精講
Boost是為C++語言標準庫提供擴展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫,作為標準庫的后備,是C++標準化進程的開發(fā)引擎之一,是為C++語言標準庫提供擴展的一些C++程序庫的總稱2022-11-11C++實現(xiàn)LeetCode(63.不同的路徑之二)
這篇文章主要介紹了C++實現(xiàn)LeetCode(63.不同的路徑之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07C語言報錯:Null Pointer Dereference的解決方案
Null Pointer Dereference(空指針解引用)是C語言中常見且危險的內(nèi)存管理錯誤,它通常在程序試圖訪問通過空指針(NULL pointer)引用的內(nèi)存地址時發(fā)生,本文將詳細介紹Null Pointer Dereference的產(chǎn)生原因,提供多種解決方案,需要的朋友可以參考下2024-06-06C/C++實現(xiàn)發(fā)送與接收HTTP/S請求的示例代碼
HTTP(Hypertext Transfer Protocol)是一種用于傳輸超文本的協(xié)議,它是一種無狀態(tài)的、應(yīng)用層的協(xié)議,用于在計算機之間傳輸超文本文檔,通常在 Web 瀏覽器和 Web 服務(wù)器之間進行數(shù)據(jù)通信,本文給大家介紹了C/C++發(fā)送與接收HTTP/S請求,需要的朋友可以參考下2023-11-11Visual?Studio?Code?配置C、C++?文件debug調(diào)試環(huán)境的詳細過程
這篇文章主要介紹了Visual?Studio?Code?配置C、C++?文件debug調(diào)試環(huán)境,本文通過圖文并茂的形式給大家介紹的非常詳細,對大家的學(xué)習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-02-02C語言?超詳細梳理總結(jié)動態(tài)內(nèi)存管理
動態(tài)內(nèi)存是相對靜態(tài)內(nèi)存而言的。所謂動態(tài)和靜態(tài)就是指內(nèi)存的分配方式。動態(tài)內(nèi)存是指在堆上分配的內(nèi)存,而靜態(tài)內(nèi)存是指在棧上分配的內(nèi)存,本文帶你深入探究C語言中動態(tài)內(nèi)存的管理2022-03-03C語言容易被忽視的函數(shù)設(shè)計原則基礎(chǔ)
C語言的設(shè)計目標是提供一種能以簡易的方式編譯、處理低級存儲器、產(chǎn)生少量的機器碼以及不需要任何運行環(huán)境支持便能運行的編程語言.那么C語言函數(shù)設(shè)計的一般原則和技巧都是怎樣的呢,下面帶你了解2022-04-04