敲错了，是VS2010直接在打开方式里选就行
[fly]存在即是合理[/fly]
这里介绍另一种素数判定方法，原理是利用费马小定理加二次探测定理来判定素数的一种概率算法。
事实上我知道这个算法要比筛法还早一些，只是一直没有使用过，借着这个机会试了一下。
关于速度，要看你怎么定义了，如果要找出一个范围内的所有素数，它的效率是不如素数筛的；但如果只判定某一个数是否是素数，它的优势非常明显，时间复杂度可以任为是O(1)。（我的代码中实际是O(log(n))，出于简化的目的，isprime不判断4以下数）。
而空间复杂度上筛法无法与这种算法相比。这也是筛法的软肋，筛法本就是一种以空间换时间的算法。
这段代码计算1千万以内的素数需要大约16秒，可以估算，计算20亿以内大约需要近1个小时。
呵呵，算是开拓一下大家的思路吧。
程序代码：#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int isprime(int n)
{
int ps[32], a, p, x, r, t, i, j;
for(t = -1, p = n - 1; p; p >>= 1) ps[++t] = p & 1;
for(i = 0; i < 16; i++)
{
a = (rand() % (n - 2)) + 2;
for(r = 1, j = t; j >= 0; j--)
{
x = r;
r = ((long long)x * x) % n;
if(r == 1 && x != 1 && x != n - 1) return 0;
if(ps[j]) r = (long long)r * a % n;
}
if(r != 1) return 0;
}
return 1;
}
int main()
{
int i, c, t0;
srand(time(NULL));
t0 = clock();
for(c = 2, i = 5; i <= 10000000; i += 2)
c += isprime(i);
printf("count = %d\nuse time %.3f s\n", c, (double)(clock() - t0) / 1000);
return 0;
}
