快速質數演算法

Ⅰ 判斷是否為質數的快速演算法

#include<stdio.h>
#include<stdlib.h>
#define SIZE 1000000
char table[SIZE];
int prime[168]=
{
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
53, 59, 61, 67, 71, 73, 79, 83, 89, 97,101,103,107,109,113,
127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,
199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,
383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,
467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,
577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,
661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,
769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,
877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,
983,991,997
};
int init()
{
int i,j;
memset(table,1,SIZE);
table[0]=table[1]=0;
for(i=0;i<168;++i)
{
for(j=prime[i]*2;j<SIZE;j+=prime[i])
{
table[j]=0;
}
}
}
int main()
{
int i;
init();
while(scanf("%d",&i)!=EOF)
{
printf(table[i]?"yes":"no");
}
return 0;
}

Ⅱ 求質數的最優演算法

#include <stdio.h>
int main()
{ int i,j,t;
for (i=2;i<100;i++)
{ t=1;
for (j=2;j<i;j++) /找因數的范圍可以是2到一半 或者平方根，甚至 可以 比平方根小的質數，當然要建一個數組
if (i % j ==0)
{ t=0;
break;
}
if (t==1)
printf("%d\n",i);
}
return 0;
}

Ⅲ 統計一億以內質數個數的最快演算法

這段程序是Pascal語言的。計算一億以內質數個數的時間只要2.4秒。

uses sysutils;

var a:array[2..100000000]of boolean;

n,i,j:longint; t:tdatetime;

begin

readln(n); t:=now;

fillchar(a,sizeof(a),1);

for i:=2 to trunc(sqrt(n)) do

if a[i] then

begin

j:=i+i;

while j<=n do begin a[j]:=false; inc(j,i) end;

end;

j:=1; i:=3;

while i<n do

begin if a[i] then inc(j); inc(i,2) end;

writeln(j,' t=',(now-t)*86400:0:2);

end.

Ⅳ 如何算出一個數的所有質數

1、找到這個數字的平方根m=√m

2、找到不大於m的所有質數。

3、在一張自然數表上劃掉所有質數的整數倍（質數本身不劃掉）

4、把1劃掉。

5、沒有劃掉的數字就是質數。

例如，我們要找到100以內的所有質數，只需要按照下面的步驟進行：

1、計算100的平方根，是10。

2、10以內的質數有2、3、5、7

3、劃掉2、3、5、7的整數倍。首先劃掉2的倍數，如4、6、8…、98、100，然後劃掉3的倍數，如6、9、12、15、…、99， 重復的就不需要再劃掉了。然後劃掉5的倍數，7的倍數。

4、最後劃掉1。

(4)快速質數演算法擴展閱讀

質數與黎曼猜想

我們之前談到：質數與黎曼猜想之間有著千絲萬縷的聯系。1896年，法國科學院舉行比賽：徵稿證明黎曼定理。兩位年輕的數學家阿達馬和德·拉·瓦萊布桑獲得了這一殊榮。

實際上這兩位數學家並沒有證明黎曼猜想，只是獲得了一點進展，但是這一點進展就一舉證明了歐拉和勒讓德的猜想，把素數猜想變成了素數定理。黎曼猜想的威力可見一斑。

1901年，瑞典數學家科赫證明：如果黎曼猜想被證實，那麼素數定理中的誤差項c大約是√xln(x)的量級。

即便黎曼猜想被證實，人們也只是在質數規律探索的過程中更近了一步，距離真正破解質數的規律，還有很長的路要走。也許質數就是宇宙留給人類的密碼。

Ⅳ 求素數最快的演算法

如果只是求一個數是否是素數的話，那就直接用了循環判斷是否能整除。反過來如果求小於某一個數之內所有的素數的話，那是用篩法來求最為快捷。效率最高。