记录编号	600296	评测结果	AAAAA
题目名称	阶乘分解	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	0.054 s
提交时间	2025-04-25 19:47:56	内存使用	3.30 MiB

#include <cstdio>
#include <vector> 

const int MAXN = 1e6 + 10;

bool vis[MAXN];
::std::vector <int> prime;
void solve(int n) {
	for (int i = 2; i <= n; ++i) {
		if (!vis[i]) prime.push_back(i);
		for (auto p : prime) {
			if ((long long)i * p > n) break;
			vis[i * p] = 1;
			if (i % p == 0) break;  
		}
	} 
}

int n; 

int main() {
	freopen("factoriala.in", "r", stdin);
	freopen("factoriala.out", "w", stdout); 
	scanf("%d", &n);
	solve(n); 
	for (auto p : prime) {
		int c = 0;
		for (long long i = p; i <= n; i *= p) {
			c += n / i; 
		} 
		printf("%d %d\n", p, c);
	}
	return 0;
}