快捷導(dǎo)航

素?cái)?shù)判定算法的實(shí)現(xiàn)

更新時(shí)間：2014年08月28日 11:07:39 投稿：junjie

這篇文章主要介紹了素?cái)?shù)判定算法的實(shí)現(xiàn),素?cái)?shù)判定問題是一個(gè)非常常見的問題,本文介紹了常用的幾種判定方法,需要的朋友可以參考下

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ù)。

復(fù)制代碼代碼如下:

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))的算法

復(fù)制代碼代碼如下:

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.dbjr.com.cn/article/54439.htm

復(fù)制代碼代碼如下:

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ù)的和。國際上稱為陳氏定理。