数学思路
最近要开始学一些数学方面的东西了，这题作为基础题再好不过了。首先，这道题问的就是在阶乘\(N!=1*2*3*\dots *N\)中分解质因数。我们可以先求出\([1,N]\)范围内的质数，然后再来求出这个式子中质因数的次数。
memset(isPrime, true, sizeof(isPrime));
isPrime[1] = false;
for (int i = 2; i <= n; i++)
if (isPrime[i])
{
primes.push_back(i);
for (int factor = 2; factor * i <= n; factor++)
isPrime[i * factor] = false;
}
接下来，我们可以说明，在阶乘式中，对于一个素数\(p\)，它的一次项出现次数为\( \lfloor \frac {N} {p} \rfloor \)，则二次项出现的次数为\(\lfloor \frac {N} {p^2} \rfloor\)，归纳起来，可以得到：
\[ \lfloor \frac {N} {p} \rfloor + \lfloor \frac {N} {p^2} \rfloor + \lfloor \frac {N} {p^3} \rfloor + \dots + + \lfloor \frac {N} {p^{log_{p} N}} \rfloor\]
化为循环式，得到：
\[ \sum_{p^i \leq N}^{i = 1} \; \lfloor \frac {N} {p^i} \rfloor\]
详细看代码吧：
// CH3101.cpp
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#define uint unsigned int
using namespace std;
const int MX_N = 5e6 + 100;
bool isPrime[MX_N];
uint n, cs[MX_N];
vector<uint> primes;
int main()
{
scanf("%u", &n);
memset(isPrime, true, sizeof(isPrime));
isPrime[1] = false;
for (int i = 2; i <= n; i++)
if (isPrime[i])
{
primes.push_back(i);
for (int factor = 2; factor * i <= n; factor++)
isPrime[i * factor] = false;
}
int siz = primes.size();
for (int i = 0; i < siz; i++)
{
uint c = 0;
for (int num = n; num; num /= primes[i])
c += num / primes[i];
printf("%u %u\n", primes[i], c);
}
return 0;
}