质数
慢着！我赶时间
1. 试除法判断正整数 x 是否是质数：
遍历 闭区间 $[\;2\;,\;\sqrt {\rm{x}} \;]$ 中的所有数，
若 x 能被其中的某个数整除，则说明 x 不是质数；
若不能被其中任何数整除，则说明 x 是质数。
2. 试除法对正整数 x 分解质因数：
遍历闭区间 $[\;2\;,\;\sqrt {\rm{x}} \;]$ 中的所有数，
若 x 能被其中的某个数 a 整除，则 a 是 x 的一个因数。
通过 while 循环，让 x 除去所有的 a【 while( x%a == 0 ) x /= a;】，同时求出因数中 a 的个数。
继续遍历找下一个因数。
循环结束后，若找到所有因数，则 x 最终会变为 1 ( 除去了所有因数 )。
若 x 最终不为 1，则此时的 x 本身就是一个因数。
( x 中最多只有一个大于 $\sqrt {\rm{x}} \;$ 的因数)
3. 用质数筛确定闭区间 [ 1 , n ] 中质数的个数
对于每个合数，用其最小的质数将其筛除，剩下的都是质数。
三言两语无法讲清，见下文详解。
if ( 你看懂了，足够了 || 你感觉写的很烂 ) 请慢走；
else 我们坐下来慢慢唠；
一、质数与合数的定义
对于一个 大于 1 的 正整数 ，
若除了 1 和它本身之外，不能 被其他数整除，则称其为 质数 ，又称 素数 ；
若除了 1 和它本身之外，还 能 被其他数整除，则称其为 合数 。
质数 11 = 1 × 11（ 11 只能被 1 和 11 整除 ）
合数 15 = 1 × 15 = 3 × 5（ 15 能被 1 、3、5、 15 整除 ）
二、质数相关算法
( 一 ) 质数的判定 —— 试除法
1. 应用场景 —— 质数的判定：
给定正整数 x， 判断 x 是否是质数。
2. 算法思路：
根据质数定义，对于正整数 x ，
满足 x 不能被区间 $[\;2\;,\;\;x\; - \;1\;\;]$ 中的任意整数整除，
即可判断 x 为质数。
特殊判断：
对于 正整数 1 ，定义其不为质数。
对于 正整数 2 ，按照上述方法，得到区间 $[\;2\;,\;(\;2\; - \;1\;)\;]$ 。
区间内没有整数，不影响 判定 2 为质数。
3. 代码实现：
bool is_prime( int x )
{
if( x < 2 ) return false; // 正整数 1 不是质数
// 枚举从 2 到 ( x - 1 ) 的所有整数，判断其是否是 x 的因数
for( int i = 2; i < x; i++ )
if( x % i == 0 )
return false; // 若能整除，则 x 不为质数
// 当 x == 2 , 可得 for( int i = 2; i < 2; i++ ) , 不会进入循环体内
return true; // 当 x == 2，或找不到其他因数，则判断 x 是质数
}
说明：对于输入的正整数 x ，要 全部枚举 ( x - 2 ) 个可能的因子，时间复杂度 为 $O(\;n\;)$ 。
// 无注释版代码
bool is_prime( int x )
{
if( x < 2 ) return false;
for( int i = 2; i < x; i++ )
if( x % i == 0 )
return false;
return true;
}
4. 算法优化：
正整数 x 的因数都是 成对出现
例如 ：12 = 1 × 12 = 2 × 6 = 3 × 4
若正整数 d1 能整除 x，则 相应的 d2 = ( x / d1 ) 也能整除 x
例如 ：2 能整除12，则 6 = 12 / 2 ，也能整除 12
因此在枚举的过程中，
我们只枚举一对因数中 较小 的因数即可。
即最多只要枚举到 $\sqrt x $ 。
$$
{d_1}\;\; \le \;\;{d_2} = \frac{x}{{{d_1}}}
$$
5. 代码实现：
bool is_prime( int x )
{
if( x < 2 ) return false; // 正整数 1 不是质数
// 只枚举较小的因数，i <= x / i
for( int i = 2; i <= x / i; i++ )
if( x % i == 0 )
return false;
return true;
}
注意事项 ：判断时有 等号 ，即 i <= x / i
因为存在两个因数相等的情况，例如：9 = 3 × 3 。
若不包含等号，则导致当 i == 3 时 for 循环条件要求 i < 3 ，
导致不能进入循环体，使得因数 3 被遗漏。
说明 ：优化后因数 i 会枚举到 $\sqrt x $ ，时间复杂度为 $O\;(\;\sqrt n \;)$
（ 一定会枚举到 $\sqrt x $ ，时间复杂度是固定的 ）
6. 补充：纠正 几种 不合适 的 for 循环的写法
// 按照算法思路枚举到 √x
for( int i = 2; i <= sqrt(x); i++ )
// 不推荐这么写
// 因为每次条件判断都要调用 sqrt() 函数
// 而调用这个函数是很慢的
// i <= √x 的变体
for( int i = 2; i * i <= n; i++ )
// 不推荐这么写
// 因为若 n 比较大，i * i 可能在开始时满足条件，
// 但随着 i 的增大 ( i++ ) ，i * i 可能因为太大而溢出
( 二 ) 分解质因数——试除法
1. 分解质因数定义：
每个 合数 都可以写成 几个质数相乘 的形式，其中每个质数都是这个合数的 因数 。
分解质因数 就是把一个合数分解成 若干个因数的乘积的形式 的过程。
例如：$360\;{\rm{ = }}\;2\; \times \;2\; \times \;2\; \times \;3\; \times \;3\; \times \;5\;{\rm{ = }}\;{2^3}\; \times \;{3^2}\; \times \;{5^1}$
2. 应用场景 —— 分解质因数：
给定正整数 x ，将其 从小到大 分解为若干个质数的乘积。
3. 算法思路：
分解质因数 只针对合数 ，但对于质数也可以写成 1 × 其自身的 乘积形式 。
质数：$5\;{\rm{ = }}\;1\; \times \;5$
朴素方法，对于正整数 x ，从小到大 尝试其 所有可能 的因数。
4. 代码实现：
void divide( int x )
{
if( x == 1 ) printf( "%d %d\n", 1, 1 ); // 特殊处理 1
for( int i = 2; i <= x; i++ ) // 最小的因数是 2，所以 i 初始值为 2
if( x % i == 0 ) // 找到一个因数
// 只要条件成立，i 一定是质数
{
int s = 0;
while( x % i == 0 ) // 循环判断 x 中有多少个相同的因数 i ( 例如 8 = 2 * 2 * 2 )
{
x /= i; // 整个 for 循环结束后，x == 1
s++;
}
printf( "%d %d\n", i, s ); // 输出因数及其次数
}
}
说明：朴素算法时间复杂度为 $O(\;n\;)$ 。
// 无注释版代码
void divide( int x )
{
if( x == 1 ) printf( "%d %d\n", 1, 1 );
for( int i = 2; i <= x; i++ )
if( x % i == 0 )
{
int s = 0;
while( x % i == 0 )
{
x /= i;
s++;
}
printf( "%d %d\n", i, s );
}
}
5. 可能存在疑问：
分解质因数是将合数写成若干个 质数的乘积 ，
但 for 循环中枚举的所有数中 包含合数 ，会不会产生错误？是否应该枚举所有的质数？
错误：$220\;{\rm{ = }}\;2\; \times \;10\; \times \;11$
正确：$220\;{\rm{ = }}\;2\; \times \;2\; \times \;5\; \times \;11$
实际上，上述的错误并不存在。
在 for 循环中，
对于 x，当枚举到 i 时，x 中已经不包含任何 $[\;2\;,\;i\; - \;1\;]$ 中的质因子了。
while( x % i == 0 )
{
x /= i; // 整个 for 循环结束后，x == 1
s++;
}
在上述错误示例中，在对因数 2 的枚举过程中，算法已经找出了所有的 2 和 5 。
若因数 10 ( 2 × 5 ) 仍存在，则说明 x 中还有因数 2 或 5 ，与实际不符。
也正因为如此，对于使得 if( x % i == 0 ) 条件成立的因数 i ，
它不会包含区间 $[\;2\;,\;i\; - \;1\;]$ 中的任意因子（ 之前的 whlie 循环已经除干净了 ）
即：只要 if( x % i == 0 ) 条件成立，i 一定是质数。
6. 算法优化：
上述朴素算法时间复杂度为 $O(\;n\;)$ 。
对于质数 x ，最多只有一个大于 $\sqrt x $ 的因数。
证明：若 x 有两个大于 $\sqrt x $ 的因数，则它们的乘积就大于 x ，矛盾。
因此质因子可以先从 2 枚举到 $\sqrt x $ ，
若还未分解完，则剩下的就一定是那个大于 $\sqrt x $ 的因数，单独处理。
7. 代码实现：
void divide( int x )
{
if( x == 1 ) printf( "%d %d\n", 1, 1 );
// x 中最多只有一个大于 sqrt(n) 的因子，因此循环只枚举到 sqrt(n)
for( int i = 2; i <= x / i; i++ )
if( x % i == 0 )
{
int s = 0;
while( x % i == 0 )
{
x /= i;
s++;
}
printf( "%d %d\n", i, s );
}
// 若 x 还有剩余，则这个值就是那个大于 sqrt(n) 的因子
if( x > 1 ) printf( "%d %d\n", x , 1 );
cout << endl;
}
说明：优化后时间复杂度为 $O(\;{\log _2}n\;)\;—\;O(\;\sqrt n \;)$
例如 $x = {2^n}$，则在第一个 for 循环的 while 循环中，
就完成了 x 的分解，此时的时间复杂度最小，为 $O(\;\log n\;)$
( 三 ) 质数筛
1. 应用场景：
给定一个正整数 n，求出 1 ~ n 中质数的个数。
2. 算法思想：
正整数 1 不是质数。
对于区间 $[\;2\;,\;n\;]$ 形成的正整数序列，
从小到大遍历序列，若当前数 i 存在，
则删除其在区间 $[\;2\;,\;n\;]$ 内的所有的倍数。
遍历结束，剩下的数便是质数。
3. 算法证明：
当遍历到正整数 i ，此时 i 仍然存在，
则说明 i 不是区间 $[\;2\;,\;i\; - 1\;]$ 中任何数的倍数，
即 区间 $[\;2\;,\;i\; - 1\;]$ 中不存在 i 的因数，
因此 i 为质数。
4. 代码实现；
const int N = 1000010;
int cnt; // 存储质数的个数 ( cnt 初值为 0 )
bool st[N];
// st[a] == false 表示正整数 a 还在整数序列中
// st[a] == true 表示正整数 a 已经被删除
void get_primes( int n )
{
for( int i = 2; i <= n; i++ )
{
if( !st[i] ) // 正整数 i 还在整数序列中
{
cnt++; // 正整数 i 是一个质数，质数个数加一
}
// 删除 i 的倍数
for( int j = i + i; j <= n; j += i ) st[j] = true;
}
}
5. 【估算】算法时间复杂度：
对于区间 $[\;2\;,\;n\;]$ 中的每一个正整数，都删除了其倍数
对于整数 2，删除其所有倍数，操作数为 ( n / 2 )
对于整数 3，删除其所有倍数，操作数为 ( n / 3 )
······
对于整数 n，删除其所有倍数，操作数为 ( n / n )
$$ \begin{array}{l} 1 + \frac{n}{2} + \frac{n}{3} + \frac{n}{4} + {\rm{\cdot\cdot\cdot + }}\frac{n}{{\rm{n}}} = n \times (\;1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + {\rm{\cdot\cdot\cdot + }}\frac{1}{{\rm{n}}}\;) = n \times \sum\limits_{i = 1}^n {\frac{1}{i}} \\\\ \mathop {\lim }\limits_{n \to \infty } \;\;n \times \sum\limits_{i = 1}^n {\frac{1}{i}} = n \times [\;\ln \;(n + 1) + \gamma \;]\\\\ \;欧拉常数:\;\gamma \approx 0.5772156 \ldots \end{array} $$
又 $n\;\ln n = n{\log _e}n < n{\log _2}n$
所以可以近似将算法时间复杂度看作 $O(\;n\log n\;)$
6. 算法优化：
实际上不需要删除区间 $[\;2\;,\;n\;]$ 中的 每一个 正整数的 所有 倍数，
仅需要删除 质数的倍数 即可。
原因：
一个合数，一定是某个质数的倍数，
因此在处理质数的倍数时，这个合数就已经被删除。
7. 代码实现：
void get_primes( int n )
{
for( int i = 2; i <= n; i++ )
{
if( !st[i] )
{
cnt++;
// 在遇到质数时，删除质数的倍数
for( int j = i + i; j <= n; j += i ) st[j] = true;
}
}
}
说明：算法时间复杂度为 $O(\;\log (\;\log n\;)\;)$
( 四 ) 质数筛 —— 线性筛法
1. 算法思路：
上述算法中，
朴素 的质数筛，筛除了 每个数 的所有 倍数 ；
优化 后的质数筛，筛除了 每个质数 的所有 倍数 。
朴素算法中，合数 30 分别被 2 / 3 / 5 / 6 / 10 / 15 这些 因数 筛除了一边
优化算法中，合数 30 分别被 2 / 3 / 5 这些 质因数 筛除了一边
筛除的 对象减少 是算法优化的关键。
但是在每个质数的所有倍数中，仍有合数被 重复 地筛除。
如果能 让每个合数只被筛除一次，就能再次提高算法效率。
一个正整数，不是质数就是合数。
同时，每个合数只有一个最小质因数。
线性筛法核心：通过合数的最小质因子删除该合数。
2. 代码实现：
int cnt; // 存储质数的个数
int primes[N]; // 存储质数
bool st[N];
// st[a] == false 表示正整数 a 还在整数序列中
// st[a] == true 表示正整数 a 已经被删除
void get_primes( int n )
{
for( int i = 2; i <= n; i++ )
{
if( !st[i] ) primes[ cnt++ ] = i; // 两层含义
// 在数组 primes 中存储质数 i
// 记录质数的数量 cnt++
// 枚举已经找到的质数
for( int j = 0; primes[j] <= n / i; j++ ) // 注意循环的结束条件
{
st[ primes[j] * i ] = true; // 筛除合数 primes[j] * i
if( i % primes[j] == 0 ) break; // 若条件成立，primes[j] 一定是 i 的最小因子
}
}
}
说明：
( 1 ) 枚举质数时循环的判断条件：primes[j] <= n / i
因为每次删除的合数为 primes[j] * i ，
若 primes[j] > n / i ，则删除了大于 n 的数，超过范围 $[\;1\;,\;n\;]$ 。
( 2 ) 为什么要删除 primes[j] * i ？
算法的 核心思路 是利用合数的 最小质因数 来删除合数。
对于当前枚举的数 i，
if( i % primes[j] == 0 ) break; 有两种结果。
因为 从小到大 枚举所有找到的质数 ，
若 i % primes[j] == 0 ，
则当前质数 primes[j] 一定 是 i 的最小质因数，
因此当前质数 primes[j] 一定是 primes[j] * i 的最小质因数，
因此删除合数 primes[j] * i 。
若 i % primes[j] != 0 ，
则当前质数 primes[j] 一定 小于 i 的最小质因数，
则当前质数 primes[j] 仍然 一定是 primes[j] * i 的最小质因数，
因此删除合数 primes[j] * i 。
因此在 break 之前，每个删除的 primes[j] * i 都是 通过 最小质 因数删除 的。
也正因为如此，当 i 的最小质因数已经确定，
那之后的质数就 一定 不是 i 的最小质因数，
也就 不一定 是 primes[j] * i 的最小质因数，因此 break 。
( 3 ) 任何一个合数 x 一定会被筛掉。
因为 x 一定存在一个最小质因子
假设 primes[j] 是 x 的最小质因子，当 i 枚举到 x / primes[j] 时，
便会删除合数 x 。
综上所述，
任何一个合数会被筛掉，
且一定是通过最小因子筛除，
而每个合数 x 只有一个最小因子，
因此 合数 x 只会被筛除一次。
因此这种算法被称为 线性筛法 。
补充：
( 1 ) if( i % primes[j] == 0 ) break;
使得质数 primes[j] 的下标不会超过 cnt 。
若 i 是质数，则 i 已经被加入到 primes 数组中，
当遍历到质数 i 则会结束循环。
若 i 是合数，在 prime 数组中已经包含了所有小于 i 的质数，
所以在从小到大枚举质数的过程中，一定能找到 i 的质因数。
因此枚举过程中，primes[j] 的下标 j 不会超过 cnt 。
( 2 ) 枚举质数时，for 循环中 primes[j] <= n / i 的条件判断是必要的。
上述提到 if( i % primes[j] == 0 ) break;
已经能处理所有的数，不管是质数还是合数最终都能退出循环。
但是当 i 和 primes[j] 都遍历到很大的数时，
primes[j] * i 可能会超出 st[N] 的下标范围，造成段错误。
三、参考资料
（接受批评指正，欢迎交流补充~~ XD）
