急速求10分钟 检验质数的算法的程序

用从2 到round(sqrt(i))的每个数去除i，如果除尽则不是质数，如是都除不尽则是质数

输出1～100之间的质数

program zx(input,output)

var

i,j:integer

flag:boolean

begin

for i:=2 to 100 do

begin

flag:=true

for j:=2 to round (sqrt(i)) do {用2到i的平方厅行根去除i，看能否除尽槐乎}

if i mod j=0 then flag:=false

if flag then write (i)

end

end.

以上是铅伏悉一段PASCAL程序，输出1～100之间的质数

把for(int i=20i<=100i+=2)

改成for(int i=20i<喊野=100i+=1)

或者for(int i=21i<=100i+=2)

lz的意思是要找出从20-100之间的所有质数，但做渗罩是这个范围的质数只能是奇数，因此，纯闹i每次要加1，如果i的初值是21，那么i就可以每次加2了。

#include <stdio.h>

#include <math.h>

#include <time.h>

#include <memory.h>

#define BLOCKSIZE 150150

#define ST 6

//2*3*5*7*11*13 * 5 = 150150

//#define BLOCKSIZE 510510 // 2*3*5*7*11*13*17=510510

clock_t tstart

void Send2Log(__int64 nMax, __int64 PrimeCnt){

double duration = (double)(clock() - tstart) / CLOCKS_PER_SEC

printf(">%7.3f秒\t计算到%11I64u\t查出素数:%10I64u个\n", duration, nMax, PrimeCnt)

}

int main()

{

int i, j, p

//旁码罩运闹 unsigned int QRT//the square root of the end of current block

// unsigned int Start//the first multiple of a prime in current block

unsigned int BasePrime[BLOCKSIZE] = { 2 }//store the first prime block

unsigned __int64 PrimeCnt = 1//prime counter

unsigned __int64 KPoint = 0//the start of current block

bool BaseTpl[BLOCKSIZE]//the block template

bool CurBuf[BLOCKSIZE]//current block

tstart = clock()

memset(BaseTpl, true, BLOCKSIZE)

// int bqrt = (int)sqrt(BLOCKSIZE) + 1

BaseTpl[1] = false

for (i = 1i * i <模纳 BLOCKSIZEi += 2){

if (BaseTpl[i] == true){

BasePrime[PrimeCnt++] = i

for (j = i * ij <BLOCKSIZEj += i * 2)

BaseTpl[j] = false

}

}

while (i <BLOCKSIZE){

if (BaseTpl[i] == true)

BasePrime[PrimeCnt++] = i

i += 2

}

//printf("prime number = %I64d, max primer = %d \n",PrimeCnt,BasePrime[PrimeCnt-1] )

memset(BaseTpl, true, BLOCKSIZE)

for (i = 1i <STi++){

for (p = BasePrime[i]p <BLOCKSIZEp += BasePrime[i]* 2)

BaseTpl[p] = false

}

for (j = 1j <BLOCKSIZEj++){

memcpy(CurBuf, BaseTpl, BLOCKSIZE)

//KPoint = (unsigned __int64)k * BLOCKSIZE

KPoint += BLOCKSIZE

const unsigned int QRT = (unsigned int)sqrt((long double)(KPoint + BLOCKSIZE)) + 1

if (j % 1000 == 0)

Send2Log(KPoint, PrimeCnt)

for (i = STp = BasePrime[i], (unsigned)p <QRTp = BasePrime[++i]){ //the 7th prime is 19.

unsigned int Start = (unsigned int)(p - (KPoint - 1) % p) - 1

const unsigned int p2 = p <<1

if ((Start &1) == 0)

Start += p

// if ((unsigned __int64)p * p >KPoint)

// Start = (unsigned __int64)p * p - KPoint

while (Start <BLOCKSIZE){

CurBuf[Start] = false

Start += p2

}

}

for (i = 1i <BLOCKSIZEi += 2){

if (CurBuf[i] == true)

//if(PrimeCnt <BLOCKSIZE) BasePrime[PrimeCnt] = KPoint + i

PrimeCnt++

}

}

// Send2Log(KPoint, PrimeCnt)

return 0

}

运算效果：

> 1.250秒 计算到 150150000 查出素数: 8452428个

> 2.562秒 计算到 300300000 查出素数: 16267724个

> 3.906秒 计算到 450450000 查出素数: 23875495个

> 5.281秒 计算到 600600000 查出素数: 31354503个

> 6.656秒 计算到 750750000 查出素数: 38739831个

> 8.062秒 计算到 900900000 查出素数: 46052992个

> 9.500秒 计算到 1051050000 查出素数: 53307936个

.....

1.该程序会一直计算下去

2.计算300300000 内的素数只需2.562秒 ，绝对满足你的要求

3.程序我也不怎么懂！！！

---