c++ 求7千万到1亿的质数，速度要快

#include<stdio.h>
#include<math.h>
#define N 100000000//只能处理200000000以内的数
int a[N];

void prime(unsigned long n) //用筛法将不是素数的值置0
{
unsigned long i,j;
a[0]=1; //2是唯一的偶素数,另作打算
for(i=3;i<=n;i+=2) //将大于2小于或等于n的奇数
a[i/2]=1;
for(i=3;i<=n/3;i+=2) //只要考虑小于n/3的就可以了,因为乘以2就是偶数,至少也是乘以3,大于n/3的就不用判断
{
if(a[i/2])
for(j=i*3;j<=n;j+=2*i) //j的奇数倍的数全部筛选出去
a[j/2]=0;
}
}

int main()
{
unsigned long n;
while(scanf("%ld",&n)){
prime(n);
if(n==2)
printf("%ld是素数\n",n);
else
if(n%2==0)
printf("%ld不是素数\n",n);
else
if(a[n/2]==1)
printf("%ld是素数\n",n);
else
printf("%ld不是素数\n",n);
}
return 0;
}

说一个优化算法。

建立一个筛子。第一次运算建立筛子。

比如，若大小为210，那么首先排除其中2、3、5、7的倍数