试除法判断质数

分解质因数

一个数可以被分解为质因数乘积

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;
}