阶乘分解

问题 A: 阶乘分解

时间限制: 1 Sec  内存限制: 128 MB

题目描述

给定整数N(1≤N≤10^6)，试把阶乘N!分解质因数，按照算术基本定理的形式输出分解结果中的pi和ci即可。

输入

一个整数N。

输出

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

样例输入

复制样例数据

5

样例输出

2 3
3 1
5 1

提示

5! = 120 = 2^3 * 3 * 5

筛素数，求<=N的所有素数出现的个数

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int prim[80005], vis[1000005], n, tot;

void get_prim(int x){
	for (int i = 2; i <= x; i++){
		if(!vis[i]) prim[tot++] = i;
		for (int j = 0; j < tot && prim[j] * i <= x; j++){
			vis[prim[j] * i] = 1;
			if(i % prim[j] == 0) break;
		}
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	get_prim(n);
	for (int i = 0; i < tot; i++){
		LL t = prim[i]; //注意t可能超过int型
		LL ans = 0;// 同上
		while(t <= (LL)n){
			ans += n / t;
			t *= prim[i];
		}
		printf("%d %lld\n", prim[i], ans);
	}

	return 0;
}
/**/