由浅入深的素数求法

什么是素数

素数(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，而是到 $\sqrt{n}$
我们以数字16为例来讲解一下，显然16的因数有1/2/4/8/16,其中 $16 = 2 * 8 = 4 * 4$ ，在isPrime函数的循环中判断到i = 8是不是因数时，其实i = 2这个对称的情况已经判断过，所以没必要再重新判断一次。这样一来我们会发现当循环中i超过 $\sqrt{n}$ 这个因子，若是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( $\sqrt{n}$ )，如果总共要判断n个数，那么时间复杂度就分别是O(n^2)和O( $n\sqrt{n}$ )。哇，这也太慢了

于是有了打印素数表法，典型空间换时间。假如我要判断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];
}