Princípio
A dceomposição em fatores primos de um inteiro é feita por divisões sucessivas (trial division).

Complexidade
\(O(\sqrt{n})\) ou, com otimizações, \(O\left(\frac{\sqrt{n}}{\ln(\sqrt{n})}\right)\).

Fatoração de um fatorial \(N!\)

Dado um inteiro \(N\), decomponha \(N!\) em fatores primos e exiba cada base \(p_i\) com seu respectivo expoente \(c_i\), segundo o teorema fundamental da aritmética.
Exemplo para \(N = 5\):
2 3
3 1
5 1

Abordagem ingênua

Aplicar a fatoração individual a cada número de 2 até \(N\) resulta em complexidade aproximada \(O(n\sqrt{n})\). Para \(N\) em torno de \(10^6\), isso provoca estouro de tempo.

#include <iostream>
using namespace std;

const int MAX = 1e6 + 10;
int expoentes[MAX];

void decompor(int n) {
    for (int d = 2; d * d <= n; ++d) {
        if (n % d == 0) {
            int cont = 0;
            while (n % d == 0) {
                ++cont;
                n /= d;
            }
            expoentes[d] += cont;
        }
    }
    if (n > 1) ++expoentes[n];
}

int main() {
    int n; cin >> n;
    for (int i = 2; i <= n; ++i) decompor(i);
    for (int i = 2; i <= n; ++i)
        if (expoentes[i]) cout << i << ' ' << expoentes[i] << endl;
}

Solução eficiente

Em vez de decompor cada número, calcula-se diretamente a contriubição de cada número primo no fatorial.

Fundamento
A quantidade de vezes que um primo \(p\) aparece em \(N!\) é dada por:

[ \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \dots + \left\lfloor \frac{n}{p^k} \right\rfloor ] onde \(p^k \le n\) e \(p^{k+1} > n\). Esse somatório é calculado em \(O(\log_p n)\) operações. Como a quantidade de primos até \(n\) é aproximadamente \(\frac{n}{\ln n}\), a complexidade total fica em \(O(n)\).

Etapas

1. Obter todos os primos até \(N\) com o crivo linear.
2. Para cada primo \(p\), somar os quocientes sucessivos de \(N\) por \(p\), \(p^2\), etc.

#include <iostream>
using namespace std;

const int LIMITE = 1e6 + 10;
int lista_primos[LIMITE], total_primos;
bool composto[LIMITE];

void crivo(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!composto[i]) lista_primos[total_primos++] = i;
        for (int j = 0; lista_primos[j] * i <= n; ++j) {
            composto[lista_primos[j] * i] = true;
            if (i % lista_primos[j] == 0) break;
        }
    }
}

int main() {
    int n; cin >> n;
    crivo(n);

    for (int idx = 0; idx < total_primos; ++idx) {
        int p = lista_primos[idx];
        int expoente = 0;
        for (int temp = n; temp; temp /= p)
            expoente += temp / p;
        cout << p << ' ' << expoente << endl;
    }
}