试除法判断质数
分解质因数
一个数可以被分解为质因数乘积
n = ，其中的pi都是质因数
那么怎么求pi及其指数呢？
我们将i一直从2~n/i循环，如果 n%i==0，那么i一定是质因数，并且用一个while循环将n除以i，一直到不能整除为止。
那么如何保证每次插入的i一定是质因数呢？i从2~n/i，那i有可能是合数呀？
我们用反证法来证明，
假如此时有i是合数，并且n%i==0。因为i是合数，那么一定有i = a*b，a!=1 && a<i，b!=1 && b<i。而如果n%i==0，那么一定也有n%a==0，n%b==0。
a，b比i更早出现，n在先前肯定已经被a和b整除到不能整除了为止，后续不可能再出现n%a==0和n%b==0的情况！矛盾了，因此当n%i==0时，i不可能是合数，一定是质数。
void solve() {
int n; cin >> n;
map<int, int> mp;
for (int i = 2; i <= n / i; i++) {
while (n % i == 0) {
mp[i]++;
n /= i;
}
}
if (n > 1) mp[n]++;
for (auto it : mp) {
cout << it.first << " " << it.second << endl;
}
}筛质数
朴素筛法
时间复杂度 O(nlogn)
将st初始化为false，假设1~N都是质数。
每遍历一个i，都将其倍数记录为合数，即st[j] = true
int p[N];
bool st[N];
void get_primes() {
int n; cin >> n;
int cnt = 0;
for (int i = 2; i <= n; i++) {
if(!st[i]) {
p[cnt++] = i;
}
for (int j = 2 * i; j <= n; j += i) {
st[j] = true;
}
}
cout << cnt<<endl;
}埃式筛法
时间复杂度 O(nloglogn)，很接近线性了
对于上面的朴素筛法，可以发现不需要对每个数都进行筛倍数，只需要对质数筛即可，因为任何一个合数都会先被他的最小质因子筛掉。所以只需将筛倍数的循环放到 if 里面即可。
int p[N];
bool st[N];
void get_primes() {
int n; cin >> n;
int cnt = 0;
for (int i = 2; i <= n; i++) {
if(!st[i]) {
p[cnt++] = i;
for (int j = 2 * i; j <= n; j += i) {
st[j] = true;
}
}
}
cout << cnt<<endl;
}线性筛
时间复杂度 O(n)
思路跟埃式筛差不多，都是只对质数筛即可，
但埃式筛还是会有点浪费，因为可能对同一个合数重复访问了。
例如：n = 100，1<ai<=n。当对质数3和质数7筛的时候，都会筛到21。
而线性筛不会，线性筛的核心思想是ai只会被其最小的质因数筛掉，确保确保每个合数只会被其最小质因子筛选一次。
核心代码是这个
if (i % primes[j] == 0) break;当 i % pj == 0 时，pj 一定是 i 的最小质因子，因此 pj 一定是 pj * i 的最小质因子。
当 i % pj != 0 时，pj 一定小于 i 的最小质因子，因此 pj 一定是 pj * i 的最小质因子。
进一步解释，
prime从小到大枚举，则 prime[j] < prime[j + 1];
如果 prime[j] 可以被i整除，那么很显然（prime[j + 1]*i）的最小质因数是 prime[j] 而不是 prime[j + 1]
再继续用 prime[j + 1] 筛，就不满足用一个数的最小质因数筛掉它这个条件了。
int primes[N];
bool st[N];
void get_primes() {
int n; cin >> n;
int cnt = 0;
for (int i = 2; i <= n; i++) {
if(!st[i]) {
primes[cnt++] = i;
}
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
//primes[j]一定是i的最小质因子（primes[j]是从小到大增长的）
}
}
cout << cnt;
}
