①先筛选出1~N的每个质数p
②N!中质因子p的个数为：
floor(N/p)+floor(N/p2)+floor(N/p3)+…+floor(N/pfloor(logpN))=Σ(pk≤N)floor(N/pk)

时间复杂度：O(NlogN)

N! 分解质因数后的结果，共若干行，每行一对pi​,ci​。按照pi从小到大的顺序输出。

#include<iostream>
#include<cmath>
using namespace std;
const int N = 1000000 + 10; 
int prime[N];
int n, m;
void primes(int n){
	for (int i = 2; i <= n; i++){
		if (!prime[i]){ prime[++prime[0]] = i; }

		for (int j = 1; j <= prime[0] && i*prime[j] <= n; j++){
			prime[i*prime[j]] = 1;
			if (i%prime[j] == 0){ break; }
		}
	}
}

int main(){
	cin >> n;
	primes(n);
	/*for (int i = 0; i <= prime[0]; i++){
		cout << prime[i] << " ";
	}
	cout << endl;
	*/
	for (int i = 1; i <= prime[0]; i++){
		int p = prime[i];
		int t = 0;
		for (int j = 1; pow(p, j) <= n; j++){
			t += n / pow(p, j);
		}
		cout << p << " " << t << endl;
	}

	return 0;
}