求出3到50w范圍內所有的素數。

這類問題在C語言題目中經常會遇見。同樣，大素數的研究對于密碼學也起到了重要的作用。那么對于C語言的初學者，該如何編寫程序計算素數呢？

1.

首先從素數的定義來看，“一個大于1的自然數，如果除了1和它自身外，不能被其他自然數整除的數”。除了一和他自身外，沒有其他因數，那么最粗暴的算法就出來了：

遍歷所有所有大于一，小于他自身的整數，如果沒有數能整除他，他就是素數。

#include

#include

int

main(){

int i,j,a,b;

a=clock();

for(i=3;i<500000;i++){

for(j=2;j

if(i%j==0){

goto table;

}

}

table:;

}

b=clock();

printf("%d\n",b-a);

return 0;

}

上述代碼就是實現了這個算法，當出現因數，直接跳到下一個數字。

經過測試，執行該代碼的時間是33449ms。

明顯對于一個求素數的算法來說，時間太長了。如果范圍擴大到5000000，甚至50000000，耗費時間更是無法想象。那么如何去改進呢？

2.

讓我們再從定義去看。“因數”，我們要尋找的是除了自身與1沒有因數的數字。而除了自身的平方根，因數都是成對存在的。而且這些因數對，一定是一大一小(除平方根)。那么我們只要保留上面的遍歷，但將遍歷的最大值設為所有因數對較小值中的最大值就可以了。只要這個值不存在，就說明該數字不存在因數對。那么自然也就是素數了。

#include

#include

#include

int main(){

int i,j,a,b;

a=clock();

for(i=3;i<500000;i++){

for(j=2;j<=sqrt(i);j++){

if(i%j==0){

goto table;

}

}

table:;

}

b=clock();

printf("%d\n",b-a);

return 0;

}

因數對中的較小值的最大值，自然就是其自身的平方根了。在這之后的因數都能對應一個在這之前的因數。所以如果在這之前沒有因數，那么在這之后也同樣沒有因數。

這可以說是個相當大的改進了，大大減少了遍歷次數，程序執行時間為234ms。

3.

除了2以外，所有的素數都是奇數。那么我們就可以先將偶數排除，再來判定質數

#include

#include

#include

int main(){

int i,j,a,b;

a=clock();

for(i=3;i<500000;i++){

if(i%2==0) goto table;

for(j=3;j<=sqrt(i);j+=2){

if(i%j==0){

goto table;

}

}

table:;

}

b=clock();

printf("%d\n",b-a);

return 0;

}

因為先一步排除了偶數， 所以尋找因數便不必再遍歷偶數因數。因為奇數的因數一定是奇數。

進一步的優化，現在程序執行時間僅有109ms。

4.

我們做數學題時，都知道平方根并不好算。同樣對于計算機來說，平方根計算也會消耗大量時間。所以我們可以先一步計算平方根，以使其不用在每次比較時都去計算。

#include

#include

#include

int main(){

int i,j,a,b;

double sq;

a=clock();

for(i=3;i<500000;i++){

if(i%2==0) goto table;

sq=sqrt(i);

for(j=3;j<=sq;j+=2){

if(i%j==0){

goto table;

}

}

table:;

}

b=clock();

printf("%d\n",b-a);

return 0;

}

這樣程序的執行時間又縮短了一倍，現在只有46ms了。

5.

不要以為數論就是一堆沒用的理論知識。算術基本定理，現在是用上它的時候了。

任何一個大于1的自然數

N,如果N不為質數，那么N可以唯一分解成有限個質數的乘積。

那么我們只需要遍歷素數因數就好了嘛。

至于能成為因數的0素數有哪些呢？

不要忘了我們是從小到大尋找的素數，現在可以用到前面的結果了。#include

#include

#include

int ar[300000];

int main(){

int i,j,k=0,a,b;

double sq;

a=clock();

for(i=3;i<500000;i++){

if(~i&1) goto table;

sq=sqrt(i);

for(j=0;ar[j]<=sq&&j

if(i%ar[j]==0){

goto table;

}

}

ar[k]=i;

k++;

table:;

}

b=clock();

printf("%d\n",b-a);

return 0;

}

把前面每一個素數放入一個數組，以此來尋找素數因數。

現在整個程序的執行時間只需要15ms了！

從最開始的3萬3千毫秒，到現在的15毫秒，整整縮短了2200多倍。可見算法對于一個程序是多么重要。

最后再貼上一段程序，思考一下這一段與上一段有什么區別，以及為什么要這么做

#include

#include

#include

int

ar[300000];

int

main(){

int i,j,k=0,a,b;

double sq;

ar[0]=2;

a=clock();

for(i=3;i<5000000;i++){

if(~i&1) goto table;

sq=sqrt(i);

for(j=0;ar[j]<=sq;j++){

if(i%ar[j]==0){

goto table;

}

}

ar[k]=i;

k++;

table:;

}

b=clock();

printf("%d\n",b-a);

return 0;

}

總結

以上是生活随笔為你收集整理的整数n分解成素数乘积c语言,关于几种求素数的方法（C语言描述）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。