由浅入深的素数求法
什么是素数
素数(primenumber)又称质数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。所以素数其实是从2开始的，如2、3是质数，0和1不在这个判定范围内。
最简单（暴力）的素数求法
bool isPrime(int n){
if (n < 2) return false; // 小于2时不考虑
if (n == 2) return true; // 等于2直接判断是素数
for (int i = 2; i < n; i++){
if (n % i == 0) return false; // 如果存在1和n之外的因数直接判断n不是素数
}
return true; // 不存在1和n之外的因数则可以判断n是素数
}
暴力素数求法的加速版本
上面的暴力求法应该非常好理解，使用的是符合正常判断逻辑的完整过程，比较好想。
同时也非常容易看出判断每一个n是否为素数的过程时间复杂度为O(n)，这是我们不希望看到的，这样一个简单操作就达到O(n)的话写别的算法题很容易导致总时间复杂度达到O(n^2)甚至O(n^3)
那么有什么好办法可以省略一部分不去考虑呢？答案当然是可以省略
先给出结论，isPrime函数中的循环条件i并不需要判断到n，而是到
我们以数字16为例来讲解一下，显然16的因数有1/2/4/8/16,其中，在isPrime函数的循环中判断到i = 8是不是因数时，其实i = 2这个对称的情况已经判断过，所以没必要再重新判断一次。这样一来我们会发现当循环中i超过
这个因子，若是n的因数，则在前半段必然判断过一次，若不是因数也没有判断的必要。
于是可以把函数修改为
bool isPrime(int n){
if (n < 2) return false;
if (n == 2) return true;
for (int i = 2; i <= (int)sqrt(n); i++){// 注意这里1. i可以取等 2.根号n要转为int型
if (n % i == 0) return false;
}
return true;
}
打印素数表法（埃式素数筛）
看到这里聪明的你肯定会想：“啊，这样靠循环来判断一个数有没有其他因数也太慢了吧，要是我一下子要判断1~10000中哪些是素数，这方法真是弱爆了”
哈哈，还真是
判断一个数是否为质数，第一个方案时间复杂度为O(n)，第二个方案时间复杂度为O()，如果总共要判断n个数，那么时间复杂度就分别是O(n^2)和O(
)。哇，这也太慢了
于是有了打印素数表法，典型空间换时间。假如我要判断100以内的素数，显然2的倍数（特指k>=2的整数倍，以下提到倍数同样）全都是合数，同理3的倍数、4的倍数也都是合数。此时我们维护一个visited数组，记录每个数字i是否是合数，如果是合数我们就不用再进行操作，如果i是素数，就把i的倍数位置全部标记为合数直到i=100判断完。
bool visited[N] = {0}; // N是自己指定的大小，最好比需要的大小再大一点点，比如10->15 100->110 1000->1010
// 一开始都赋值为0 表示都是质数， 相对的当visited[i]==1则表示i是合数
void printPrimeTable(){
for (int i = 2; i <= n; i ++){
if (!visited[i]){
for (int j = i * 2; j <= n; j += i){
visited[j] = 1;
}
}
}
}
bool isPrime(int n){
return !visited[i];
}
查看25道真题和解析