链接:
https://www.acwing.com/problem/content/199/
题意:
给定整数 N ，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的 pi 和 ci 即可。
思路:
对于n!, 考虑1-n的质数, 对于每个质数,p^k在n!出现的次数为n/(p^k).
计算k时, 会计算k+1,的次数, 所以每个只用加一次.
代码:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+10;
int IsPri[MAXN], Pri[MAXN];
long long Cnt[MAXN];
int pos, n;
void Euler()
{
memset(IsPri, 0, sizeof(IsPri));
memset(Pri, 0, sizeof(Pri));
memset(Cnt, 0, sizeof(Cnt));
IsPri[1] = 1;
pos = 0;
for (int i = 2;i <= n;i++)
{
if (IsPri[i] == 0)
Pri[++pos] = i;
for (int j = 1;j <= pos && Pri[j]*i <= n;j++)
{
IsPri[Pri[j]*i] = 1;
if (i%Pri[j] == 0)
break;
}
}
}
int main()
{
scanf("%d", &n);
Euler();
for (int i = 1;i <= pos;i++)
{
long long tmp = Pri[i];
while (tmp <= n)
{
Cnt[i] += n/tmp;
tmp *= Pri[i];
}
}
for (int i = 1;i <= pos;i++)
printf("%d %lld\n", Pri[i], Cnt[i]);
return 0;
}