两种筛素数的方法

筛选法求素数：

void getprime()

{

int i,j;

memset(b,1,sizeof(b));

b[0]=0;

b[1]=0;

for(i=2;i*i<=100000;i++)

{

if(b[i])

{

for(j=i*i;i<=100000;j+=i)

{

p[j]=0;

}

}

}

}

快速判断一个数是否为素数

bool isPrime(int num)

{

if (num == 2 || num == 3)

{

return true;

}

if (num % 6 != 1 && num % 6 != 5)

{

return false;

}

for (int i = 5; i*i <= num; i += 6)

{

if (num % i == 0 || num % (i+2) == 0)

{

return false;

}

}

return true;

}

快速求一个数以内的所有素数

#define N 100000000

 

bool notPrime[N+5];

 

void ScreeningPrime(void)

{

int i, j, increment[6] = {0, 4, 0, 0, 0, 2};

for (i = 5; i*i <= N; i += increment[i%6])

{

for (j = i; i*j <= N; j += increment[j%6])

{

notPrime[i*j] = true;

}

}

}