质数问题
# 背景
质数指的是除了1和它本身，没有其他因数的数。 本文讨论质数的三类问题，判断质数、打印质数表、分解质因数。
# 判断质数
判断n是否为质数，我们使用试除法判断，从2开始找因子，找到
bool isPrime(int x) {
if (x <= 1) return false; // 边界特判
for (int i = 2; i <= sqrt{n}; i++) {
if (n % i == 0) return false;
}
return true;
}
2
3
4
5
6
7
我们看28=4*7，正整数n的因数必然是成对出现的，一个小于等于
# 打印质数表
给定一个正整数n，打出1到n中的所有质数。
我们很自然地会想到将判断质数的函数拿过来用。
遍历1到n，对每个数调用一次isPrime，时间复杂度为
for (int i = 1; i <= n; i++) {
if (isPrime(i)) cout << i << endl;
}
2
3
我们考虑下上述暴力方法存在什么问题。
我们看两个数：289(17 * 17), 323(17 * 19)。判断这两个数是否是质数，isPrime函数中因子会从2找到17。这两个数有一个共同的因子17，如果我们看到17后，将它的倍数全部筛除，效率就会高得多。
# 埃氏筛法
#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
bool v[N]; // false 表示没有被筛除
int main(void) {
int n;
cin >> n;
for (int i = 2; i <= n; i++) { // 枚举因数
if (!v[i]) { // 如果i没有被筛除，表示它是质数
cout << i << endl;
for (int j = 2; i * j <= n; j++) { // 枚举倍数，计算乘积i * j
v[i * j] = true;
}
}
}
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
在这个代码中，我们枚举因数，只有当它为质数时，才去筛除它的倍数。 解释：考虑4的倍数一定是2的倍数，所以4能筛掉的数，2肯定也能筛掉。
这个算法仍然不是线性时间复杂度，每个合数并不是只被筛除一次，比如：
30会被哪些数筛掉呢？30有2、3、5三个质因子，所以会被筛掉3次。
我们来计算下时间复杂度，我们会使用1->n内的所有质数去做筛除，质数x能够筛掉
# 另一种写法
在这种写法中，我们枚举倍数，结合质数表中数去做筛选。
#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
bool v[N];
int prime[N];
int p;
int main(void) {
int n;
cin >> n;
for (int i = 2; i <= n; i++) { // 枚举2->n中的所有数，作为倍数
if (!v[i]) { // 如果该数没有被筛选掉，则是质数，记录在质数表里
cout << i << endl;
prime[++p] = i;
}
for (int j = 1; j <= p && i * j <= n; j++) { // 枚举质数表中的质数，筛除倍数i与各质数的乘积
v[i * prime[j]] = true;
}
}
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
这个代码能够保证倍数i一定大于质数prime[j]，优于第一种写法，举个例子：
15 = 3 * 5在第一种写法中，15会被3和5筛除两次。
在当前写法中15只会被筛除一次15 = 3(质数) * 5(倍数)
然而该写法仍然不是线性时间复杂度。 30 = 2(质数) * 15(倍数) 30 = 3(质数) * 10(倍数) 30 = 5(质数) * 6(倍数) 在满足倍数>质数的情况下，30仍然被筛除3次。
# 欧拉筛法
我们给上一个代码加一个魔法😄
#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
bool v[N];
int prime[N];
int p;
int main(void) {
int n;
cin >> n;
for (int i = 2; i <= n; i++) { // 枚举2->n中的所有数，作为倍数
if (!v[i]) { // 如果该数没有被筛选掉，则是质数，记录在质数表里
cout << i << endl;
prime[++p] = i;
}
for (int j = 1; j <= p && i * j <= n; j++) { // 枚举质数表中的质数，筛除倍数i与各质数的乘积
v[i * prime[j]] = true;
if (i % prime[j] == 0) break; // 当i是质数表中某个质数的倍数时，跳出循环 魔法！！！
}
}
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
魔法能够使得每个数只被最小的质因子筛除。 例如：30就只会以2(质数) * 15(倍数)的形式被筛除。
我们来看看30 = 3(质数) * 10(倍数)这种筛选方式为什么不存在：
倍数i = 10，此时prime数组中有[2, 3, 5, 7]四个质数。
当j = 1时，prime[j] = 2, i是2的倍数，此时跳出j的for循环。
就不会枚举到下一个质数了，也就不存在3 * 10的筛选方案了。
形式化分析下：当i能够被prime[j]整除时，i = k * prime[j] 如果j的for循环进行到下一轮，被筛掉的数就会是i(倍数) * prime[j + 1](质数) = (k * prime[j])(倍数) * prime[j + 1](质数) 这个数明显可以被一个更小的质数prime[j]删除。 所以加了break之后，我们就能够保证每个合数一定是被最小质因子筛掉的了。
每个数都只被筛选一次，算法时间复杂度为
# 分解质因数
我们使用除因子法分解质因数
#include <bits/stdc++.h>
using namespace std;
int main(void) {
int n;
cin >> n;
for (int i = 2; i <= sqrt(n); i++) {
while (n % i == 0) { // 某一个质因子可能出现多次
cout << i << endl;
n /= i; // 除去因子
}
}
if (n > 1) cout << n; // 可能还剩一个因数
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
例如： 28 = 2 * 2 * 7，因子2只能在for循环中被去除掉，因子7在if判断中被拿出。
for循环执行完只会剩一个质因子，我们反证法来说明。
若存在两个相等因子5 * 5，那么n就是25，5 <= sqrt(25)，for循环会将这两个因子除去。
若存在两个不等因子5 * 7，那么n就是35，5 <= sqrt(35)，5会在for循环中被除去。
那么分解质因数有什么意义呢？
- 可以用于判断A是否为B的因数。当A中所有质因子的数量都小于等于B中对应质因子的数量时，A就是B的因数。 例如： A = 12 = 2 * 2 * 3 B = 180 = 2 * 2 * 3 * 3 * 5 对于质因子2，3，5来说，A中数量都比B中数量少，A是B的因数。
判断因数为什么不使用模运算？ 因为有些时候题目中给我的试一个乘法的表示形式，计算结果可能非常大。 比如问你a是否是b的q次幂的因数，a, b, q均为正整数。 b的q次幂用一般的int、long long可能都存不下，使用高精度模拟的话更麻烦，这个时候就可以用这条性质啦。
- 可以用于求因数的个数
180 = 2 * 2 * 3 * 3 * 5180的质因子包含2个2，2个3，1个5。 我们从这些数中选一部分做乘积，得到的就是180的因数。
180中有2个2，我们可以选0个，1个，2个，3种方案。 180中有2个3，我们可以选0个，1个，2个，3种方案。 180中有1个5，我们可以选0个，1个，2种方案。 按照分步乘法原理，我们可以得到这样的组合共有3 * 3 * 2 = 18种。 所以，180不同的因数共有18个。