一億以內質數最快演算法

㈠ 怎麼找質數最快

首先記住常用的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