素數(shù)判定算法的實現(xiàn)
1. 素數(shù)判定問題
素數(shù)判定問題是一個非常常見的問題，本文介紹了常用的幾種判定方法。
2. 原始算法
素數(shù)的定義是，除了能被1和它本身整除而不能被其他任何數(shù)整除的數(shù)。根據(jù)素數(shù)定義 只需要用2到n-1去除n，如果都除不盡，則n是素數(shù)，否則，只要其中有一個數(shù)能整除則n不是素數(shù)。
bool is_primer1(int num) {
int i;
for(i = 2; i < num; i++) {
if(num % i == 0) {
return true;
}
}
return false;
}
3. 改進算法
n不是素數(shù)，則n可表示為a*b，其中2<=a<=b<=n-1,則a，b中必有一個數(shù)滿足：1<x<=sqrt(n)，因而，只需要用2~sqrt(n)去除n，這樣就得到一個復(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. 篩選算法
更高效地素數(shù)判斷方法應(yīng)該是將素數(shù)預(yù)先保存到一個素數(shù)表中，當判斷一個數(shù)是否為素數(shù)時，直接查表即可。這種方法需要解決兩個問題：
(1) 怎樣快速得到素數(shù)表？（采用篩選方法）
(2) 怎樣減少素數(shù)表的大小？（采用位圖數(shù)據(jù)結(jié)構(gòu)）
對于1到n全部整數(shù)，逐個判斷它們是否是素數(shù)，找出一個非素數(shù)，就把它挖掉，最后剩下的就是素數(shù)。具體方法是：
<1> 定義is_primer[i] = true;
<2> 從2開始，依次遍歷整個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://chabaoo.cn/article/54439.htm
bool load_primer_table1() { //保存素數(shù)表
int i;
for(i = 1; i < INT_MAX; i++) {
if(i % 2 != 0 //偶數(shù)一定不是素數(shù)
&& is_primer2(i)) {
set(i);
}
}
}
bool load_primer_table2() {//另一種更快的方法保存素數(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) { //查表判斷是否為素數(shù)
if(test(num))
return true;
return false;
}
5. 優(yōu)化的篩選算法
(1) 存儲方式優(yōu)化
仍然采用位圖方式存儲，只不過是位圖中只存儲奇數(shù)，這樣一下子節(jié)省了一半空間（需要的空間僅為4G/(32*2)=64MB）
存儲空間優(yōu)化后，算法效率也會提升很多，如：1,2，…,30
只需存儲3,5,7,9,11,13,15,17,19,21,23,25,27,29
i=0, is_primer[0] =true, 把下標[3][6][9][12]，即9,15,21,27,標為false
i=1, s_primer[0] =true,把下標為[6][11],即15,25標為false
i=2, 2*i+3>sqrt(30),結(jié)束
即：i=s, 把下標為s(2*t+1)+3t,其中，t=1,2,3，…中所有的的is_primer置為false
(2) 優(yōu)化刪選算法
a是素數(shù)，則下一個起點是a*a,把后面的所有的a*a+2*i*a篩掉。即欲求n以內(nèi)的素數(shù)，就先把sqrt(n)內(nèi)的素數(shù)求出來，用已經(jīng)求得的素數(shù)來篩出后面的合數(shù)。
6. 總結(jié)
至今為止，沒有任何人發(fā)現(xiàn)素數(shù)的分布規(guī)律，也沒有人能用一個公式計算出所有的素數(shù)。關(guān)于素數(shù)的很多的有趣的性質(zhì)或者科學(xué)家的努力，如：
(1) 高斯猜測，n以內(nèi)的素數(shù)個數(shù)大約與n/ln(n)相當，或者說，當n很大時，兩者數(shù)量級相同。這就是著名的素數(shù)定理。
(2) 十七世紀費馬猜測，2的2^n次方+1，n=0，1，2…時是素數(shù)，這樣的數(shù)叫費馬素數(shù)，可惜當n=5時，2^32+1就不是素數(shù)，至今也沒有找到第六個費馬素數(shù)。
(3) 18世紀發(fā)現(xiàn)的最大素數(shù)是2^31-1，19世紀發(fā)現(xiàn)的最大素數(shù)是2^127-1，20世紀末人類已知的最大素數(shù)是2^859433-1，用十進制表示，這是一個258715位的數(shù)字。
(4) 孿生素數(shù)猜想：差為2的素數(shù)有無窮多對。目前知道的最大的孿生素數(shù)是1159142985×2^2304－1和1159142985×2^2304＋1。
(5) 歌德巴赫猜想：大于2的所有偶數(shù)均是兩個素數(shù)的和，大于5的所有奇數(shù)均是三個素數(shù)之和。其中第二個猜想是第一個的自然推論，因此歌德巴赫猜想又被稱為1+1問題。我國數(shù)學(xué)家陳景潤證明了1+2，即所有大于2的偶數(shù)都是一個素數(shù)和只有兩個素數(shù)因數(shù)的合數(shù)的和。國際上稱為陳氏定理。
相關(guān)文章
這篇文章主要介紹了C/C++中的OpenCV讀取視頻與調(diào)用攝像頭，具有很好的參考價值，希望對大家有所幫助。2022-11-11
Opencv學(xué)習(xí)教程之漫水填充算法實例詳解
這篇文章主要給大家介紹了Opencv學(xué)習(xí)教程之漫水填充算法的相關(guān)資料，文中給出了詳細的示例代碼供大家參考學(xué)習(xí)，對大家具有一定的參考價值，需要的朋友們下面跟著小編一起來學(xué)習(xí)學(xué)習(xí)吧。2017-06-06
本文主要介紹了C++實現(xiàn)一個簡單的線程池的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05
HDOJ 1443 約瑟夫環(huán)的最新應(yīng)用分析詳解
本篇文章是對HDOJ 1443 約瑟夫環(huán)的最新應(yīng)用進行了詳細的分析介紹，需要的朋友參考下2013-05-05
下面小編就為大家?guī)硪黄獪\談C語言函數(shù)調(diào)用參數(shù)壓棧的相關(guān)問題。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2021-10-10
歸并排序是比較穩(wěn)定的排序方法。它的基本思想是把待排序的元素分解成兩個規(guī)模大致相等的子序列。本文將用C++實現(xiàn)這一排序算法，需要的可以參考一下2022-09-09
在C++中，mutable也是為了突破const的限制而設(shè)置的。被mutable修飾的變量，將永遠處于可變的狀態(tài)，即使在一個const函數(shù)中2013-10-10
常見C/C++?XML解析器有Tinyxml、XERCES、squashxml、xmlite、pugxml、libxml等等，本文為大家介紹的是使用TinyXml實現(xiàn)讀取XMl文件，需要的可以參考一下2023-06-06
這篇文章主要介紹了基于C語言實現(xiàn)的迷宮游戲代碼,對于學(xué)習(xí)游戲開發(fā)的朋友相信有一定的借鑒價值,需要的朋友可以參考下2014-08-08
這篇文章主要為大家詳細介紹了Qt實現(xiàn)進程界面之間的鼠標焦點切換，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-09-09