·1不是质数
·2是唯一的偶质数(除2以外的质数都必然是奇数)
·若 2 ~ sqrt(n) 之间没有能够整除 n 的数,则 2 ~ n 之间没有数能整除 n
根据以上性质:
1.我们可以单独处理 2
2.筛选质数时我们只需要检测奇数就行
3.试除法验证“n”是否为质数时,只需试除区间“2 ~ sqrt(n)”
C++代码实现:
if(…)
{
cout << 2 << endl;
return 0;
}
for(int i = 3;; i += 2)
{
bool flag = true;
for(int j = 3; j*j <= i; j += 2)
{
if(i % j == 0)
{
flag = false;
break;
}
}
if(flag)
{
……
}
}