素數剖斷算法的完成。本站提示廣大學習愛好者：（素數剖斷算法的完成）文章只能為提供參考，不一定能成為您想要的結果。以下是素數剖斷算法的完成正文
1. 素數剖斷成績
素數剖斷成績是一個異常罕見的成績，本文引見了經常使用的幾種剖斷辦法。
2. 原始算法
素數的界說是，除能被1和它自己整除而不克不及被其他任何數整除的數。依據素數界說 只須要用2到n-1去除n，假如都除不盡，則n是素數，不然，只需個中有一個數能整除則n不是素數。
bool is_primer1(int num) {
int i;
for(i = 2; i < num; i++) {
if(num % i == 0) {
return true;
}
}
return false;
}
3. 改良算法
n不是素數，則n可表現為a*b，個中2<=a<=b<=n-1,則a，b中必有一個數知足：1<x<=sqrt(n)，因此，只須要用2~sqrt(n)去除n，如許就獲得一個龐雜度為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. 挑選算法
更高效地素數斷定辦法應當是將素數事後保留到一個素數表中，當斷定一個數能否為素數時，直接查表便可。這類辦法須要處理兩個成績：
(1) 如何疾速獲得素數表？（采取挑選辦法）
(2) 如何削減素數表的年夜小？（采取位圖數據構造）
關於1到n全體整數，逐一斷定它們能否是素數，找出一個非素數，就把它挖失落，最初剩下的就是素數。詳細辦法是：
<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
為了削減內存應用率，算法應用了位圖數據構造，關於位圖，可參考：http://www.jb51.net/article/54439.htm
bool load_primer_table1() { //保留素數表
int i;
for(i = 1; i < INT_MAX; i++) {
if(i % 2 != 0 //偶數必定不是素數
&& is_primer2(i)) {
set(i);
}
}
}
bool load_primer_table2() {//另外一種更快的辦法保留素數表
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) { //查表斷定能否為素數
if(test(num))
return true;
return false;
}
5. 優化的挑選算法
(1) 存儲方法優化
依然采取位圖方法存儲，只不外是位圖中只存儲奇數，如許一會兒節儉了一半空間（須要的空間僅為4G/(32*2)=64MB）
存儲空間優化後，算法效力也會晉升許多，如：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),停止
即：i=s, 把下標為s(2*t+1)+3t,個中，t=1,2,3，…中一切的的is_primer置為false
(2) 優化刪選算法
a是素數，則下一個終點是a*a,把前面的一切的a*a+2*i*a篩失落。即欲求n之內的素數，就先把sqrt(n)內的素數求出來，用曾經求得的素數來篩出前面的合數。
6. 總結
至今為止，沒有任何人發明素數的散布紀律，也沒有人能用一個公式盤算出一切的素數。關於素數的許多的風趣的性質或許迷信家的盡力，如：
(1) 高斯猜想，n之內的素數個數年夜約與n/ln(n)相當，或許說，當n很年夜時，二者數目級雷同。這就是有名的素數定理。
(2) 十七世紀費馬猜想，2的2^n次方+1，n=0，1，2…時是素數，如許的數叫費馬素數，惋惜當n=5時，2^32+1就不是素數，至今也沒有找到第六個費馬素數。
(3) 18世紀發明的最年夜素數是2^31-1，19世紀發明的最年夜素數是2^127-1，20世紀末人類已知的最年夜素數是2^859433-1，用十進制表現，這是一個258715位的數字。
(4) 孿生素數料想：差為2的素數有沒有窮多對。今朝曉得的最年夜的孿生素數是1159142985×2^2304－1和1159142985×2^2304＋1。
(5) 歌德巴赫料想：年夜於2的一切偶數均是兩個素數的和，年夜於5的一切奇數均是三個素數之和。個中第二個料想是第一個的天然推論，是以歌德巴赫料想又被稱為1+1成績。我國數學家陳景潤證實了1+2，即一切年夜於2的偶數都是一個素數和只要兩個素數因數的合數的和。國際上稱為陳氏定理。
