【算法基础篇】（四十）数论之算术基本定理深度剖析：从唯一分解到阶乘分解

#include <iostream>
#include <unordered_map>
using namespace std;

// 分解质因数，返回质因子及其指数（键为质因子，值为指数）
unordered_map<int, int> prime_factor(int x) {
    unordered_map<int, int> factors;
    // 枚举到sqrt(x)即可
    for (int i = 2; i <= x / i; ++i) {
        if (x % i == 0) { // i是x的质因子
            int cnt = 0;
            while (x % i == 0) { // 除尽所有i
                cnt++;
                x /= i;
            }
            factors[i] = cnt;
        }
    }
    // 剩余的x如果大于1，说明是最后一个质因子（大于sqrt(原x)）
    if (x > 1) {
        factors[x] = 1;
    }
    return factors;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    auto factors = prime_factor(n);
    // 按质因子从小到大输出
    cout << n << " = ";
    bool first = true;
    for (auto [p, cnt] : factors) {
        if (!first) cout << " × ";
        cout << p << "^" << cnt;
        first = false;
    }
    cout << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

const int MAXN = 1e6 + 10;
int min_prime[MAXN]; // 存储每个数的最小质因子
vector<int> primes;  // 存储所有质数

// 线性筛预处理最小质因子
void sieve(int n) {
    memset(min_prime, 0, sizeof min_prime);
    primes.clear();
    for (int i = 2; i <= n; ++i) {
        if (min_prime[i] == 0) { // i是质数
            min_prime[i] = i;
            primes.push_back(i);
        }
        // 枚举所有质数，更新i*primes[j]的最小质因子
        for (int j = 0; j < primes.size() && primes[j] <= min_prime[i] && i * primes[j] <= n; ++j) {
            min_prime[i * primes[j]] = primes[j];
        }
    }
}

// 利用最小质因子分解x
unordered_map<int, int> fast_prime_factor(int x) {
    unordered_map<int, int> factors;
    while (x > 1) {
        int p = min_prime[x]; // x的最小质因子
        int cnt = 0;
        while (x % p == 0) {
            cnt++;
            x /= p;
        }
        factors[p] = cnt;
    }
    return factors;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int max_range = 1e6;
    sieve(max_range); // 预处理1e6以内的最小质因子
    
    int n;
    while (cin >> n) {
        auto factors = fast_prime_factor(n);
        cout << n << " = ";
        bool first = true;
        for (auto [p, cnt] : factors) {
            if (!first) cout << " × ";
            cout << p << "^" << cnt;
            first = false;
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1e4 + 10;
int cnt[MAXN]; // cnt[p]表示质因子p在N!中的指数

// 试除法分解单个x的质因数，并累加指数到cnt数组
void decompose(int x) {
    for (int i = 2; i <= x / i; ++i) {
        while (x % i == 0) {
            cnt[i]++;
            x /= i;
        }
    }
    if (x > 1) {
        cnt[x]++;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    memset(cnt, 0, sizeof cnt);
    
    // 对1~N的每个数分解质因数，累加指数
    for (int i = 2; i <= N; ++i) {
        decompose(i);
    }
    
    // 输出所有有贡献的质因子（cnt[p]>0）
    for (int p = 2; p <= N; ++p) {
        if (cnt[p] > 0) {
            cout << p << " " << cnt[p] << endl;
        }
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 1e6 + 10;
bool st[MAXN]; // 标记是否为合数
int primes[MAXN], cnt_primes; // 存储质数，cnt_primes为质数个数

// 线性筛筛选[2, n]的所有质数
void sieve(int n) {
    memset(st, false, sizeof st);
    cnt_primes = 0;
    for (int i = 2; i <= n; ++i) {
        if (!st[i]) {
            primes[++cnt_primes] = i;
        }
        for (int j = 1; 1LL * i * primes[j] <= n; ++j) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) {
                break;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    sieve(N); // 筛选[2, N]的所有质数
    
    // 对每个质数计算其在N!中的指数
    for (int i = 1; i <= cnt_primes; ++i) {
        int p = primes[i];
        int a = 0;
        long long current = p;
        while (current <= N) {
            a += N / current;
            current *= p; // 计算p^2, p^3, ...
        }
        cout << p << " " << a << endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int MAXN = 1e6 + 10;
bool st[MAXN];
int primes[MAXN], cnt;

// 线性筛优化版（筛选质数并存储）
void get_primes(int n) {
    memset(st, 0, sizeof st);
    cnt = 0;
    for (int i = 2; i <= n; ++i) {
        if (!st[i]) {
            primes[++cnt] = i;
        }
        // 优化：用long long避免i*primes[j]溢出
        for (int j = 1; 1LL * i * primes[j] <= n; ++j) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    get_primes(N);
    
    for (int i = 1; i <= cnt; ++i) {
        int p = primes[i];
        int ci = 0;
        LL current = p;
        while (current <= N) {
            ci += N / current;
            // 防止current溢出（当p=2，N=1e6时，current最大为2^19=524288，不会溢出）
            if (current > N / p) break; // 提前判断，避免current*p溢出
            current *= p;
        }
        cout << p << " " << ci << endl;
    }
    return 0;
}