阶乘分解

AcWing-197-阶乘分解

分析

见《进阶指南》第138页。

实现

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1000010;
int idx, primes[N];
bool mark[N];

void get_primes (int n) {
    for (int i = 2; i <= n; ++ i) {
        if (mark[i] == false) primes[++ idx] = i;
        for (int j = 1; primes[j] <= n / i; ++ j) {
            mark[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main () {
    int n;
    cin >> n;
    get_primes(n);
    for (int i = 1; i <= idx; ++ i) {
        int copy_n = n, p = primes[i], e = 0;
        while (copy_n > 0) {
            e += (copy_n / p);
            copy_n /= p;
        }
        cout << p << ' ' << e << endl;
    }
    return 0;
}