}
 

3：这个方法是上面方法的改进，但要求 N 平方根以下的素数已全部知道

算法 2：遍历 2 以上 N 的平方根以下的每一个素数，是不是能整除 N;

(这个方法是上面方法的改进，但要求 N 平方根以下的素数已全部知道)
void PrimeNumber2()

{
int time GetTickCount();

cout start time time endl;
 

int Max[MAX_NUMBER2]; 在栈上分配，栈上空间要求一般都在 2M 之间，

如果你需要更大空间，请在堆上申请空间(就是通过 malloc，new 来申请).素数的个数

很少
所以没有必要申请和所求数字同样大小的空间。
memset(Max,0,MAX_NUMBER);
Max[0] = 2; 放入第一个素数，有人说 2 不是素数，如果你是其中一员，就改成 3 吧

int cout = 1; 记录素数个数
 

挨个数进行验证
bool bflag = true;

for(int i = 3; i MAX_NUMBER; ++i)
{

bflag = true;

需要是使用数学库（math.h）中 sqrt

int iTemp = (int)sqrt((float)i); 强制转换成 int 类型,有的人在这里使用 i＋1 就是为了

增加 sqrt 的精度

没有特殊函数，你也可以使用 int iTemp = (int)sqrt(i)＋1;来提高进度
 

修改的是这里以下的部分
for (int j = 0; j cout; ++j)

{
if(i%Max[j] == 0) 求余，如果为 0 说明，可以整除，不是素数。

{
bflag = false;

break;
}

}

修改的是这里以上的部分
 

经过验证是素数，放入数组。
if(bflag)
{

Max[cout++] = i;
}

}
 

int time GetTickCount();
cout end time time endl;

 
}

 
4：采用 Rabin-Miller 算法进行验算，Rabin-Miller 算法是典型的验证一个数字是否为

素数的方法。判断素数的方法是 Rabin-Miller 概率测试，那么他具体的流程是什么呢。

假设我们要判断 n 是不是素数，首先我们必须保证 n 是个奇数，那么我们就可以把 n 表

 

示为 n = (2^r)s+1,注意 s 也必须是一个奇数。然后我们就要选择一个随机的整数 a