素?cái)?shù)判定算法的實(shí)現(xiàn)
1. 素?cái)?shù)判定問題
素?cái)?shù)判定問題是一個(gè)非常常見的問題，本文介紹了常用的幾種判定方法。
2. 原始算法
素?cái)?shù)的定義是，除了能被1和它本身整除而不能被其他任何數(shù)整除的數(shù)。根據(jù)素?cái)?shù)定義 只需要用2到n-1去除n，如果都除不盡，則n是素?cái)?shù)，否則，只要其中有一個(gè)數(shù)能整除則n不是素?cái)?shù)。
bool is_primer1(int num) {
int i;
for(i = 2; i < num; i++) {
if(num % i == 0) {
return true;
}
}
return false;
}
3. 改進(jìn)算法
n不是素?cái)?shù)，則n可表示為a*b，其中2<=a<=b<=n-1,則a，b中必有一個(gè)數(shù)滿足：1<x<=sqrt(n)，因而，只需要用2~sqrt(n)去除n，這樣就得到一個(gè)復(fù)雜度為O(sqrt(n))的算法
bool is_primer2(int num) {
int i;
int upper = sqrt(num);
printf("primer2:%d\n", upper);
for(i = 2; i <= upper; i++) {
if(num % i == 0) {
return true;
}
}
return false;
}
4. 篩選算法
更高效地素?cái)?shù)判斷方法應(yīng)該是將素?cái)?shù)預(yù)先保存到一個(gè)素?cái)?shù)表中，當(dāng)判斷一個(gè)數(shù)是否為素?cái)?shù)時(shí)，直接查表即可。這種方法需要解決兩個(gè)問題：
(1) 怎樣快速得到素?cái)?shù)表？（采用篩選方法）
(2) 怎樣減少素?cái)?shù)表的大?。浚ú捎梦粓D數(shù)據(jù)結(jié)構(gòu)）
對(duì)于1到n全部整數(shù)，逐個(gè)判斷它們是否是素?cái)?shù)，找出一個(gè)非素?cái)?shù)，就把它挖掉，最后剩下的就是素?cái)?shù)。具體方法是：
<1> 定義is_primer[i] = true;
<2> 從2開始，依次遍歷整個(gè)is_primer(直到sqrt(N))，如果is_primer[i]=true,則is_primer[n*i]=false
如1,2,3,4,5,6,7,8,9,10，則
從2開始遍歷：
is_primer[2]=true，則is_primer[4]= is_primer[6]= is_primer[8]= is_primer[10]= true
is_primer[3]=true，則is_primer[6]= is_primer[9]= true
為了減少內(nèi)存使用率，算法使用了位圖數(shù)據(jù)結(jié)構(gòu)，關(guān)于位圖，可參考：http://www.fzitv.net/article/54439.htm
bool load_primer_table1() { //保存素?cái)?shù)表
int i;
for(i = 1; i < INT_MAX; i++) {
if(i % 2 != 0 //偶數(shù)一定不是素?cái)?shù)
&& is_primer2(i)) {
set(i);
}
}
}
bool load_primer_table2() {//另一種更快的方法保存素?cái)?shù)表
int i, j;
for(i = 1; i <= INT_MAX; i++) {
if( i % 2) {
set(i);
} else {
clear(i);
}
}
int upper = sqrt(INT_MAX);
for(i = 1; i <= upper; i++) {
if(test(i)) {
for(j = i + i; j < INT_MAX; j += i)
set(i);
}
}
}
bool is_primer3(long num) { //查表判斷是否為素?cái)?shù)
if(test(num))
return true;
return false;
}
5. 優(yōu)化的篩選算法
(1) 存儲(chǔ)方式優(yōu)化
仍然采用位圖方式存儲(chǔ)，只不過是位圖中只存儲(chǔ)奇數(shù)，這樣一下子節(jié)省了一半空間（需要的空間僅為4G/(32*2)=64MB）
存儲(chǔ)空間優(yōu)化后，算法效率也會(huì)提升很多，如：1,2，…,30
只需存儲(chǔ)3,5,7,9,11,13,15,17,19,21,23,25,27,29
i=0, is_primer[0] =true, 把下標(biāo)[3][6][9][12]，即9,15,21,27,標(biāo)為false
i=1, s_primer[0] =true,把下標(biāo)為[6][11],即15,25標(biāo)為false
i=2, 2*i+3>sqrt(30),結(jié)束
即：i=s, 把下標(biāo)為s(2*t+1)+3t,其中，t=1,2,3，…中所有的的is_primer置為false
(2) 優(yōu)化刪選算法
a是素?cái)?shù)，則下一個(gè)起點(diǎn)是a*a,把后面的所有的a*a+2*i*a篩掉。即欲求n以內(nèi)的素?cái)?shù)，就先把sqrt(n)內(nèi)的素?cái)?shù)求出來，用已經(jīng)求得的素?cái)?shù)來篩出后面的合數(shù)。
6. 總結(jié)
至今為止，沒有任何人發(fā)現(xiàn)素?cái)?shù)的分布規(guī)律，也沒有人能用一個(gè)公式計(jì)算出所有的素?cái)?shù)。關(guān)于素?cái)?shù)的很多的有趣的性質(zhì)或者科學(xué)家的努力，如：
(1) 高斯猜測，n以內(nèi)的素?cái)?shù)個(gè)數(shù)大約與n/ln(n)相當(dāng)，或者說，當(dāng)n很大時(shí)，兩者數(shù)量級(jí)相同。這就是著名的素?cái)?shù)定理。
(2) 十七世紀(jì)費(fèi)馬猜測，2的2^n次方+1，n=0，1，2…時(shí)是素?cái)?shù)，這樣的數(shù)叫費(fèi)馬素?cái)?shù)，可惜當(dāng)n=5時(shí)，2^32+1就不是素?cái)?shù)，至今也沒有找到第六個(gè)費(fèi)馬素?cái)?shù)。
(3) 18世紀(jì)發(fā)現(xiàn)的最大素?cái)?shù)是2^31-1，19世紀(jì)發(fā)現(xiàn)的最大素?cái)?shù)是2^127-1，20世紀(jì)末人類已知的最大素?cái)?shù)是2^859433-1，用十進(jìn)制表示，這是一個(gè)258715位的數(shù)字。
(4) 孿生素?cái)?shù)猜想：差為2的素?cái)?shù)有無窮多對(duì)。目前知道的最大的孿生素?cái)?shù)是1159142985×2^2304－1和1159142985×2^2304＋1。
(5) 歌德巴赫猜想：大于2的所有偶數(shù)均是兩個(gè)素?cái)?shù)的和，大于5的所有奇數(shù)均是三個(gè)素?cái)?shù)之和。其中第二個(gè)猜想是第一個(gè)的自然推論，因此歌德巴赫猜想又被稱為1+1問題。我國數(shù)學(xué)家陳景潤證明了1+2，即所有大于2的偶數(shù)都是一個(gè)素?cái)?shù)和只有兩個(gè)素?cái)?shù)因數(shù)的合數(shù)的和。國際上稱為陳氏定理。
相關(guān)文章
這篇文章主要介紹了C++ QgraphicsScene類案例詳解,本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
Z字形變換排列就是指將一個(gè)給定字符串根據(jù)給定的行數(shù)，以從上往下、從左到右進(jìn)行 Z 字形排列，下面讓我們用C語言來實(shí)現(xiàn)2022-04-04
opencv+arduino實(shí)現(xiàn)物體點(diǎn)追蹤效果
這篇文章主要為大家詳細(xì)介紹了opencv+arduino實(shí)現(xiàn)物體點(diǎn)追蹤效果，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
Qt6+QML實(shí)現(xiàn)Windows屏幕錄制功能
Qt6提供了很多豐富的多媒體支持類,本文將為大家詳細(xì)介紹一下Qt6如何結(jié)合QML實(shí)現(xiàn)Windows屏幕錄制功能,文中的示例代碼簡潔易懂,有需要的小伙伴可以參考一下2025-04-04
C/C++根據(jù)年月日計(jì)算星期幾（蔡勒公式篇）
這篇文章主要給大家介紹了關(guān)于C/C++根據(jù)年月日計(jì)算星期幾（蔡勒公式篇）的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
這篇文章主要介紹了C++中的Lambda表達(dá)式詳解,本文講解了基本語法、Lambda的使用等內(nèi)容,需要的朋友可以參考下,希望能夠給你帶來幫助2021-10-10
C語言中結(jié)構(gòu)體(struct)的幾種初始化方法
相信大家都知道struct結(jié)構(gòu)體是C語言中非常重要的復(fù)合類型，初始化的方法很多，那么小編下面對(duì)這些方法進(jìn)行總結(jié)，便于自己和大家以后查閱,有需要的可以參考借鑒。2016-08-08
對(duì)比C語言中execv相關(guān)的執(zhí)行文件的三個(gè)函數(shù)
這篇文章主要介紹了對(duì)比C語言中execv相關(guān)的執(zhí)行文件的三個(gè)函數(shù),分別為execv()函數(shù)和execve()函數(shù)以及execvp()函數(shù),需要的朋友可以參考下2015-08-08
這篇文章主要介紹了c語言實(shí)現(xiàn)計(jì)算圓周率的近似值方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-12-12
解析C/C++指針、函數(shù)、結(jié)構(gòu)體、共用體
這篇文章主要介紹了C/C++指針、函數(shù)、結(jié)構(gòu)體、共用體的相關(guān)知識(shí)，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-01-01