快速质数算法

Ⅰ 判断是否为质数的快速算法

#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)的量级。

即便黎曼猜想被证实，人们也只是在质数规律探索的过程中更近了一步，距离真正破解质数的规律，还有很长的路要走。也许质数就是宇宙留给人类的密码。

Ⅳ 求素数最快的算法

如果只是求一个数是否是素数的话，那就直接用了循环判断是否能整除。反过来如果求小于某一个数之内所有的素数的话，那是用筛法来求最为快捷。效率最高。