CH 3101-阶乘分解

题目：

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

思路:
如果直接分别对2~N分解质因数，再将结果合成，那么时间复杂度过高会超时。显然N！的质因数不会超过N，那么先求出不超过N的所有素数p，再分别求出其在N！中的次数。对每一个素数p，其在N！中的次数等于在1~N中的次数之和。1~N中能被p整除的有⌊N/p⌋个数，能被p^2整除的有⌊N/p^2⌋个数（也就是说此时p的次数至少有⌊N/p⌋+⌊N/p^2⌋,其中⌊N/p^2⌋不必乘以2，因为被p^2整除的数也被p整除，而此前已经统计过一次p），以此类推，p的次数就有⌊N/p⌋+⌊N/p^2⌋+⌊N/p^3⌋+……+⌊N/p^⌊log(N)/log(p)⌋⌋. 每如此计算一次，时间复杂度为O(logN)，则总复杂度为O(NlogN).

代码：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>

using namespace std;
#define MAX_N 1000005

int v[MAX_N];
int prime[MAX_N];
int c[MAX_N];

int m;
void primes(int n) {
  m = 0;
  memset(v, 0, sizeof(v));
  memset(prime, 0, sizeof(prime));
  for (int i = 2; i <= n; i++) {
    if (v[i] == 0) {
      v[i] = i;
      prime[++m] = i;
    }
    for (int j = 1; j <= m; j++) {
      if (prime[j] > v[i] || prime[j] > n / i) {
        break;
      }
      v[i * prime[j]] = prime[j];
    }
  }
}

int main() {
  int n;
  cin >> n;
  primes(n);
  for (int i = 1; i <= m; i++) {
    long long p = prime[i]; //最后一次极限情况相乘可能溢出所以用ll，有点坑，找了好久
    int t = 0;
    while (n/p) {
      t += n / p;
      p *= prime[i];
    }
    c[i] = t;
  }
  for (int i = 1; i <= m; i++) {
    printf("%d %d\n", prime[i], c[i]);
  }

  return 0;
}