素数又称为质数，是一个大于1的自然数，它满足以下性质：
不能被除了1和它本身之外的其它自然数整除。即在所有自然数中，它只有1和它本身两个约数。
我们用 π ( n ) pi(n) π(n)来表示小于等于n中所有素数的个数，当n越大时， π ( n ) ∼ n l n ( n ) pi(n) sim frac n{ln(n)} π(n)∼ln(n)n。该统计学性质可以用来帮助我们判断时间复杂度要求，以及选用什么算法。
素数的判定假设需要判定一个自然数x是否为素数
暴力法 O ( n ) O(n) O(n)由于素数和合数都有一个共同点，就是1和x都能整除x，但是合数有一个素数没有的性质，就是在 2 ∼ x − 1 2 sim x - 1 2∼x−1中必有至少一个数k能够整除x，因此我们可以用暴力法枚举 i i n ( 2 t o x − 1 ) i in (2 to x - 1) i 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 x - 2 x−2次，因此时间复杂度为 O ( n ) O(n) O(n)，比较高
试除法 O ( n ) O(sqrt n) O(n )暴力法可以准确无误地判断出一个数是不是素数，但是花费的代价是否太大了呢？我们能否对它进行优化呢？
我们会发现，在
2
∼
x
−
1
2 sim x - 1
2∼x−1中，如果有
k
∈
(
2
,
x
−
1
)
k in (2,x - 1)
k∈(2,x−1)可以被x整除，那么
x
k
frac xk
kx也必将能够被
x
x
x整除。我们假设此时的
k
<
=
x
k
k <= frac xk
k<=kx，那么必然有
k
<
=
x
，
x
k
>
=
x
k <= sqrt x，frac xk >= sqrt x
k<=x
，kx>=x
，这个结论可以用反证法证明：
如果
k
>
x
，
x
k
>
=
x
k > sqrt x，frac xk >= sqrt x
k>x
，kx>=x
，那么
k
∗
x
k
=
x
>
x
k * frac xk = x > x
k∗kx=x>x恒成立，这显然是错误的
如果
k
<
=
x
，
x
k
<
x
k <= sqrt x，frac xk < sqrt x
k<=x
，kx
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; // 不是合数，则是素数
}
