一亿以内质数最快算法

㈠ 怎么找质数最快

首先记住常用的100以内的质数，其次抓住是合数的数的性质特征，至于较大数在不好判定时，可以借助质数表查询。

100以内的质数：

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

合数的数的性质特征

所有大于2的偶数都是合数。

所有大于5的奇数中，个位为5的都是合数。

除0以外，所有个位为0的自然数都是合数。

所有个位为4，6，8的自然数都是合数。

最小的（偶）合数为4，最小的奇合数为9。

每一个合数都可以以唯一形式被写成质数的乘积，即分解质因数。(算术基本定理)

1000以内质数表如下：

(1)一亿以内质数最快算法扩展阅读：

尽管整个素数是无穷的，仍然有人会问“100，000以下有多少个素数？”，“一个随机的100位数多大可能是素数？”。素数定理可以回答此问题。

1、在一个大于1的数a和它的2倍之间（即区间（a, 2a]中）必存在至少一个素数。

2、存在任意长度的素数等差数列。[1]

3、一个偶数可以写成两个合数之和，其中每一个合数都最多只有9个质因数。（挪威数学家布朗，1920年）

4、一个偶数必定可以写成一个质数加上一个合成数，其中合数的因子个数有上界。（瑞尼，1948年）

5、一个偶数必定可以写成一个质数加上一个最多由5个因子所组成的合成数。后来，有人简称这结果为 （1 + 5）（中国潘承洞，1968年）

6、一个充分大偶数必定可以写成一个素数加上一个最多由2个质因子所组成的合成数。简称为 （1 + 2）

㈡ 计算1000000(6个0)以内质数并输出,通常用时多少算高效算法

用时在不同配置上的电脑是不一样的
一般不用用时来判断程序的好坏啊，都是用复杂度的
1000000用筛选法的话很快就能出结果的~远小于1s

㈢ 怎样求10000000以内的素数，算法，要在比较短的时间内出结果。

关于素数求解，我在网络知道里面回复过几篇，颠来倒去也就这么点知识。

求解200万以内的所有素数，可以直接用厄拉多塞算法，详细情况可以参考该链接内我的回答，也就是最佳答案：http://..com/question/94494946.html，将长度修改成200万是没问题的，至少VC6上面编译通过的。

200万以上的素数，如果单纯的求解某个数是否是素数，那么用厄拉多塞+拉宾米勒+Pollard启发算法就可以AC了（参见http://..com/question/88011147.html，也是我自己的回答，所以应该不算是参考资料吧），不过如果要求解所有的素数-_-，好像有些难度哦~反正VC内的数组肯定是支持不了1亿的长度的~会崩溃的~

㈣ 统计一亿以内质数个数的最快算法

这段程序是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.

㈤ 如何用matlab求一亿内的素数

三以后的偶数都不会是质数，甚至包括五以后的以五为尾数的都不会是质数，以下代码只优化忽略检验大于二的偶数，对五为尾数的数还没忽略，并非最优代码，循环处理次数为1:100000000的一半。
A=2;
for n=3:2:100000000
if isprime(n)
A=[A,n];
end
end

补充一句，就算你数数，一秒一个，一亿秒要多久？根据3600秒一个小时算要27777.7小时，等同于1157.4天，等同于3.17年。当然计算很快，但再快，要找到一个亿以内的所有数也需要相当长时间，除非你让你的计算机够快，有这耐心等。
粗略估算了一下时间，可能是我的pc处理器时钟频率低的原因，只有1.6GHz,在采用以上算法计算十万以内的的素数时，耗时84.7350秒，以此为参考标准，一亿为十万的一千倍，所以耗时约为84735秒，等同1412.25分钟，等同23.5375小时，大概一天时间。

附加寻找十万以内素数耗时算法：
A=2;
now1=clock;
for n=3:2:100000
waitbar(n / steps)
if isprime(n)
A=[A,n];
end
end
now2=clock;
close(h)
dt=now2-now1;
time=dt(4)*60*60+dt(5)*60+dt(6)

㈥ C语言编程求素数的个数，计算1到1000000000(10亿)以内的素数个数，有多少个附上程序

不知道有没有国际最优，但我这个算法很顶尖了：计算1亿以内的素数个数不到2秒钟！1到10000000000（10亿）共有素数50847534个，计算时间大概20多秒！程序如下：#include<iostream>
using namespace std;
int main()
{int CompositeNumFilterV3(int);
int m,c;
cin>>m;
c=CompositeNumFilterV3(m);
cout<<c<<endl;
return 0;
}//求素数的程序
int CompositeNumFilterV3(int n)
{
int i, j;
//素数数量统计
int count = 0;
// 分配素数标记空间，明白+1原因了吧，因为浪费了一个flag[0]
char* flag = (char*)malloc( n+1 );
// 干嘛用的，请仔细研究下文
int mpLen = 2*3*5*7*11*13;
char magicPattern[2*3*5*7*11*13]; // 奇怪的代码，why，思考无法代劳，想！
for (i=0; i<mpLen; i++)
{
magicPattern[i++] = 1;
magicPattern[i++] = 0;
magicPattern[i++] = 0;
magicPattern[i++] = 0;
magicPattern[i++] = 1;
magicPattern[i] = 0;
}
for (i=4; i<=mpLen; i+=5)
magicPattern[i] = 0;
for (i=6; i<=mpLen; i+=7)
magicPattern[i] = 0;
for (i=10; i<=mpLen; i+=11)
magicPattern[i] = 0;
for (i=12; i<=mpLen; i+=13)
magicPattern[i] = 0; // 新的初始化方法,将2,3,5,7,11,13的倍数全干掉
// 而且采用memcpy以mpLen长的magicPattern来批量处理
int remainder = n%mpLen;
char* p = flag+1;
char* pstop = p+n-remainder;
while (p < pstop)
{
memcpy(p, magicPattern, mpLen);
p += mpLen;
}
if (remainder > 0)
{
memcpy(p, magicPattern, remainder);
}
flag[2] = 1;
flag[3] = 1;
flag[5] = 1;
flag[7] = 1;
flag[11] = 1;
flag[13] = 1; // 从17开始filter，因为2,3,5,7,11,13的倍数早被kill了
// 到n/13止的，哈哈，少了好多吧
int stop = n/13;
for (i=17; i <= stop; i++)
{
// i是合数，请歇着吧，因为您的工作早有您的质因子代劳了
if (0 == flag[i]) continue;
// 从i的17倍开始过滤
int step = i*2;
for (j=i*17; j <= n; j+=step)
{
flag[j] = 0;
}
}

// 统计素数个数
for (i=2; i<=n; i++)
{
if (flag[i]) count++;
}

// 因输出费时，且和算法核心相关不大，故略
// 释放内存，别忘了传说中的内存泄漏
free(flag);

return count;
}

㈦ 求十亿内所有质数的和，怎么做最快

计算时间应该在1秒内完成的。我的程序可以做到。#include <math.h>#include <stdio.h>#include <memory.h>#include <time.h>#define ST 7#define MOVE 4#define BLOCKSIZE (510510 * 8) // 2 * 3 * 5 * 7 * 11 * 13 * 17 = 510510#define MAXM ((BLOCKSIZE >> MOVE) + 1)#define SET_BIT(a, n) a[n >> 3] |= (1 << (n & 7))typedef unsigned int uint;typedef unsigned short ushort;typedef unsigned char uchar;typedef unsigned long long uint64;static ushort NumBit0[1 << 16];static uint Prime[6800];static uchar BaseTpl[MAXM * 2];static int sieve( ){ int primes = 1; const uint maxp = (1 << 16) + 1000; for (uint p = 3; p < maxp; p += 2) { if (0 == (BaseTpl[p >> MOVE] & (1 << (p / 2 & 7)))) { Prime[primes++] = p; for (uint i = p * p / 2; i < maxp / 2; i += p) SET_BIT(BaseTpl, i); } } return primes;}static void initBit( ){ memset(BaseTpl, 0, sizeof(BaseTpl)); for (int k = 1; k < ST; k++) for (int p = Prime[k] / 2; p < sizeof(BaseTpl) * 8; p += Prime[k]) SET_BIT(BaseTpl, p); for (int i = 1; i < sizeof(NumBit0) / sizeof(NumBit0[0]); i++) NumBit0[i] = NumBit0[i >> 1] + (i & 1); for (int j = 0; j < sizeof(NumBit0) / sizeof(NumBit0[0]); j++) NumBit0[j] = 16 - NumBit0[j];}static void inlinecrossOutFactorMod6(uchar bitarray[], const uint start, const uint leng, uint factor){ uint s2, s1 = factor - start % factor; s1 += factor - factor * (s1 % 2); if (start <= factor) s1 = factor * factor; const char skip[] = {0, 2, 1, 1, 0, 1}; const char mrid = ((start + s1) / factor) % 6 - 1; s1 = s1 / 2 + skip[mrid] * factor; s2 = s1 + skip[mrid + 1] * factor; for (factor += 2 * factor; s2 <= leng / 2; ) { SET_BIT(bitarray, s1); s1 += factor; //6k + 1 SET_BIT(bitarray, s2); s2 += factor; //6k + 5 } if (s1 <= leng / 2) SET_BIT(bitarray, s1);}static int inline setSieveTpl(uchar bitarray[], uint start, int leng){ const int offset = start % BLOCKSIZE; memcpy(bitarray, BaseTpl + (offset >> MOVE), (leng >> MOVE) + 2); if (start < 32) *((short*)bitarray) = 0x3491; //0x 0011 0100 1001 0001 bitarray[0] |= (1 << (offset % 16 / 2)) - 1; leng += offset % 16; *((uint*)bitarray + (leng >> 6)) |= ~((1u << (leng / 2 & 31)) - 1); return offset % 16;}static uint64 segmentedSieve(uint start, int leng){ uchar bitarray[MAXM + 64]; const int offset = setSieveTpl(bitarray, start, leng); start -= offset, leng += offset; const int maxp = (int)sqrt((double)start + leng) + 1; for (int i = ST, p = Prime[i]; p < maxp; p = Prime[++i]) crossOutFactorMod6(bitarray, start, leng, p); uint64 sum = 0; for (int i = 0; i < leng / 2; i ++) { if (!(bitarray[i >> 3] & (1 << (i & 7))))#if 0 printf("%u ", start + i * 2 + 1), sum ++;#else sum += start + i * 2 + 1;#endif } return sum;}int sievePrimes(uint start, uint stop){ uint64 primes = 0; if (start <= 2 && stop >= 2) { primes = 2; printf("%d ", 2); } const int segsize = 31 << 14; if (start + segsize > stop) return primes + segmentedSieve(start, stop - start + 1); primes += segmentedSieve(start, segsize - start % segsize); for (uint i = start / segsize + 1; i < stop / segsize; i++) primes += segmentedSieve(i * segsize, segsize); primes += segmentedSieve(stop - stop % segsize, stop % segsize + 1); return primes;}int main(int argc, char* argv[]){ uint start = 0, stop = 100000000; sieve(); initBit(); const char *ouput = "PI(%u, %u) = %lld, time use %u ms "; while (scanf("%u %u", &start, &stop) == 2 && start < stop ) { clock_t tstart = clock(); int primeCnt = sievePrimes(start, stop); printf(ouput, start, stop, primeCnt, clock() - tstart); } return 0;}//PI[1, 2147483647] = 105097565, time use 159

10亿也就相当于2的32次方，根据质数定理，大概有百万个左右。用数域筛法，现在的机器做起来都不算事情，蛋疼的人们早就把这些数算出来了。有个网站，http://prime.utm.e/list，基本把前500万个质数都算出来了。所以，最快的算法就是做个爬虫，然后把这些质数抓出来，至于加法的快速算法，似乎32位数也不需要。我的快速算法设计完毕。

㈧ 一亿里有几个质数

一亿内有5761455个质数

用π(x)表示不超过x的所有质数个数,有近似公式π(x)≈x/ln(x)

通过数学软件可以计算出π(x)的准确值
π(10)=4
π(100)=25
π(1000)=168
π(10000)=1229
π(100000)=9592
π(1000000)=78498
π(10000000)=664579
π(100000000)=5761455
π(1000000000)=50847534
通过数学软件计算得到一亿内最大的质数为99999989,最接近一亿的质数为100000007