素数的定义

素数又称为质数，是一个大于1的自然数，它满足以下性质：
不能被除了1和它本身之外的其它自然数整除。即在所有自然数中，它只有1和它本身两个约数。

素数计数函数

我们用 $\pi(n)$ 来表示小于等于n中所有素数的个数，当n越大时， $\pi(n) \sim \frac n{ln(n)}$ 。该统计学性质可以用来帮助我们判断时间复杂度要求，以及选用什么算法。

素数的判定

假设需要判定一个自然数x是否为素数

暴力法 $O (n)$

由于素数和合数都有一个共同点，就是1和x都能整除x，但是合数有一个素数没有的性质，就是在 $\sim x - 1$ 中必有至少一个数k能够整除x，因此我们可以用暴力法枚举 $\ in \ (2\ \ to\ \ x - 1)$ 内的所有数字来一一判定

bool is_prime(int x){ // 暴力法判定素数
	for(int i = 2; i < x; i ++) // 枚举 2 ~ x - 1
		if(x % i == 0) return false; // 如果i能被x整除，说明是合数，返回false
	return true; // 如果不是合数，返回true
}

这种思维虽然简单，但是它需要遍历 $x ? 2$ 次，因此时间复杂度为 $O (n)$ ，比较高

试除法 $O(\sqrt n)$

暴力法可以准确无误地判断出一个数是不是素数，但是花费的代价是否太大了呢？我们能否对它进行优化呢？
我们会发现，在 $\sim x - 1$ 中，如果有 $\in (2,x - 1)$ 可以被x整除，那么 $\frac xk$ 也必将能够被 $x$ 整除。我们假设此时的 $\frac xk$ ，那么必然有 $\sqrt x，\frac xk >= \sqrt x$ ，这个结论可以用反证法证明：
如果 $\sqrt x，\frac xk >= \sqrt x$ ，那么 $\frac xk = x > x$ 恒成立，这显然是错误的
如果 $\sqrt x，\frac xk < \sqrt x$ ，那么 $\frac xk = x < x$ 恒成立，这显然也是错误的。
也就是说，只要我们枚举完了所有 $\sqrt x$ ，就已经可以下结论是否存在素数了，因为当 $\sqrt x$ 时， $\sqrt x = \sqrt x$ ，即说明此时的 $x / i$ 都是已经遍历过的数值，再遍历也是多此一举。由于只要遍历 $\sqrt x$ 个数，因此时间复杂度为 $O(\sqrt n)$

bool is_prime(int x){ // 试除法判定素数
	if(x == 1) return false; // 如果x == 1，则不是素数
	for(int i = 2; i <= x / i; i ++) // 如果用i * i >= x作为判断条件的话，i*i 有可能会爆int,不太安全
		if(x % i == 0) return false; // 如果x能整除i，则是合数
	return true; // 不是合数，则是素数
}