Menurut Fundamental Theorem of Arithmetic, setiap bilangan bulat positif n > 1 dapat ditulis secara unik sebagai produk bilangan prima: n = p₁^e₁ · p₂^e₂ · ... · pₖ^eₖ. Representasi ini disebut faktorisasi prima. Banyak masalah teori bilangan — menghitung jumlah pembagi, FPB/KPK, Euler’s totient, hingga kriptografi RSA — dimulai dari faktorisasi. Pada Chapter ini kita membangun algoritma trial division O(√n), lalu memakai hasilnya untuk menghitung jumlah pembagi (d(n)) dan sum pembagi (σ(n)).

Definisi dan Teorema Fundamental #

Aturan #

Untuk n > 1, faktorisasi prima n adalah representasi:

text 
n = p₁^e₁ · p₂^e₂ · ... · pₖ^eₖ   dengan p₁ < p₂ < ... < pₖ prima, eᵢ ≥ 1

Representasi ini unik (urutan faktor diabaikan). Contoh: 360 = 2³ · 3² · 5¹. Bilangan 1 memiliki faktorisasi kosong (produk nol faktor = 1).

Mekanisme: Mengapa Trial Division Cukup Sampai √n #

Bila n memiliki faktor prima p, maka p ≤ √n — kecuali bila n itu sendiri prima, dalam hal ini sisa n akhir loop adalah prima. Maka, loop trial division berhenti saat p² > n, dan sisa n (bila > 1) adalah prima terakhir.

Algoritma Trial Division #

Aturan #

  1. Inisialisasi daftar faktor kosong, d = 2.
  2. Selama d · d ≤ n:
    • Bila n % d == 0: d prima. Bagi n dengan d berulang, hitung eksponen e, simpan (d, e).
    • Lakukan d += 1 (atau loncat genap setelah d = 2 untuk optimasi).
  3. Bila n > 1 di akhir loop, sisa n prima — simpan (n, 1).

Mekanisme: Mengapa Setiap d yang Membagi Adalah Prima #

Bila d komposit (mis. d = a · b dengan a, b > 1), maka a < d sudah membagi n di iterasi sebelumnya — sehingga n sudah dibersihkan dari faktor a, dan d tidak bisa lagi membagi. Maka, setiap d yang lolos uji n % d == 0 otomatis prima. Tidak perlu primality test terpisah.

Kode: Faktorisasi, Jumlah Pembagi, Sum Pembagi #

cpp 
#include <iostream>
#include <vector>

// Faktorisasi prima via trial division O(sqrt(n))
std::vector<std::pair<long long, int>> factorize(long long n) {
    std::vector<std::pair<long long, int>> factors;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            int e = 0;
            while (n % p == 0) { n /= p; ++e; }
            factors.push_back({p, e});
        }
    }
    if (n > 1) factors.push_back({n, 1});  // sisa prima
    return factors;
}

// Hitung jumlah pembagi dari n: prod (e_i + 1)
long long count_divisors(long long n) {
    auto f = factorize(n);
    long long r = 1;
    for (auto [p, e] : f) r *= (e + 1);
    return r;
}

// Hitung sum pembagi dari n: prod (p^(e+1) - 1) / (p - 1)
long long sum_divisors(long long n) {
    auto f = factorize(n);
    long long r = 1;
    for (auto [p, e] : f) {
        long long pk = 1, sum = 0;
        for (int i = 0; i <= e; ++i) { sum += pk; pk *= p; }
        r *= sum;
    }
    return r;
}

int main() {
    long long nums[] = {12, 60, 360, 1, 97, 1'000'000'007LL, 999'999'999LL};
    for (long long n : nums) {
        std::cout << "n = " << n << '\n';
        auto f = factorize(n);
        std::cout << "  Faktorisasi: ";
        if (f.empty()) std::cout << "(kosong)";
        for (size_t i = 0; i < f.size(); ++i) {
            auto [p, e] = f[i];
            std::cout << p;
            if (e > 1) std::cout << '^' << e;
            if (i + 1 < f.size()) std::cout << " * ";
        }
        std::cout << '\n';
        std::cout << "  Jumlah pembagi: " << count_divisors(n) << '\n';
        std::cout << "  Sum pembagi: " << sum_divisors(n) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text 
n = 12
  Faktorisasi: 2^2 * 3
  Jumlah pembagi: 6
  Sum pembagi: 28
n = 60
  Faktorisasi: 2^2 * 3 * 5
  Jumlah pembagi: 12
  Sum pembagi: 168
n = 360
  Faktorisasi: 2^3 * 3^2 * 5
  Jumlah pembagi: 24
  Sum pembagi: 1170
n = 1
  Faktorisasi: (kosong)
  Jumlah pembagi: 1
  Sum pembagi: 1
n = 97
  Faktorisasi: 97
  Jumlah pembagi: 2
  Sum pembagi: 98
n = 1000000007
  Faktorisasi: 1000000007
  Jumlah pembagi: 2
  Sum pembagi: 1000000008
n = 999999999
  Faktorisasi: 3^4 * 37 * 333667
  Jumlah pembagi: 20
  Sum pembagi: 1534205464
  1. Baris for (long long p = 2; p * p <= n; ++p): loop sampai √n. Saat p melampaui √n, n yang tersisa (bila > 1) harus prima.
  2. Baris while (n % p == 0) { n /= p; ++e; }: habiskan semua kemunculan p di n. Setelah loop, n tidak lagi mengandung faktor p.
  3. Baris if (n > 1) factors.push_back({n, 1});: sisa n setelah loop trial division adalah prima (tidak ada pembagi ≤ √n_asli). Masukkan sebagai faktor terakhir dengan eksponen 1.
  4. Baris for (auto [p, e] : f) r *= (e + 1);: rumus d(n) = ∏(eᵢ + 1). Setiap faktor pᵢ^eᵢ berkontribusi eksponen 0..eᵢ (yaitu eᵢ + 1 pilihan).
  5. Baris long long pk = 1, sum = 0;: hitung 1 + p + p² + ... + p^e = (p^(e+1) - 1)/(p - 1). Iteratif O(e) (lebih aman dari formula geometris yang bisa overflow).
  6. Hasil n = 12: 2² · 3, d(12) = (2+1)(1+1) = 6: pembagi 1, 2, 3, 4, 6, 12 (enam). Sesuai.
  7. Hasil sum_divisors(12) = 28: 1+2+3+4+6+12 = 28. Sesuai.
  8. Hasil n = 1: faktorisasi kosong, d(1) = 1 (hanya 1 sendiri), σ(1) = 1. Konvensi yang konsisten.
  9. Hasil n = 999999999 = 3⁴ · 37 · 333667: d = (4+1)(1+1)(1+1) = 20. Sesuai.

Aplikasi Faktorisasi #

Jumlah Pembagi d(n) #

text 
d(n) = (e₁ + 1) · (e₂ + 1) · ... · (eₖ + 1)

Setiap faktor prima pᵢ^eᵢ dapat muncul di pembagi dengan eksponen 0, 1, ..., eᵢ — total eᵢ + 1 pilihan. Total kombinasi adalah produk.

Sum Pembagi σ(n) #

text 
σ(n) = (1 + p₁ + p₁² + ... + p₁^e₁) · ... · (1 + pₖ + ... + pₖ^eₖ)
     = ∏ (pᵢ^(eᵢ+1) - 1) / (pᵢ - 1)

Bilangan n disebut sempurna bila σ(n) = 2n. Contoh: 6 = 1+2+3, 28 = 1+2+4+7+14.

Euler’s Totient φ(n) #

text 
φ(n) = n · ∏ (1 - 1/pᵢ)  = ∏ (pᵢ^eᵢ - pᵢ^(eᵢ-1))

Hitung banyak bilangan 1 ≤ k ≤ n dengan gcd(k, n) = 1. Implementasi langsung dari faktorisasi.

Faktorisasi untuk n Sangat Besar #

Aturan #

Trial division O(√n) praktis hingga n ≈ 10¹² (~10⁶ iterasi). Untuk n lebih besar (mis. n 30-digit dari RSA modulus), trial division terlalu lambat. Diperlukan algoritma khusus:

  • Pollard’s rho: algoritma probabilistik O(n^(1/4)) per faktor. Cukup untuk n hingga ~10¹⁸.
  • Quadratic sieve: sub-eksponensial, untuk n ~10⁵⁰.
  • General Number Field Sieve (GNFS): tercepat untuk n ~10¹⁰⁰+ (digunakan untuk memfaktorkan RSA-2048 dalam praktik).

Pollard’s rho: Sketsa #

Pollard’s rho menggunakan iterasi x_{i+1} = (x_i² + c) mod n dan mencari gcd(|x_i - x_2i|, n) berulang. Berkat birthday paradox, pola siklus muncul dalam O(√p) langkah di mana p faktor prima terkecil — jauh lebih cepat dari O(√n) saat p << n.

Ringkasan #

  • Faktorisasi prima: n = p₁^e₁ · ... · pₖ^eₖ, unik untuk n > 1.
  • Trial division: loop p dari 2 sambil p² ≤ n, habiskan eksponen, sisa n > 1 adalah prima terakhir. Kompleksitas O(√n).
  • Jumlah pembagi d(n) = ∏(eᵢ + 1).
  • Sum pembagi σ(n) = ∏(pᵢ^(eᵢ+1) - 1)/(pᵢ - 1), atau hitung iteratif 1 + p + ... + p^e per faktor.
  • Untuk faktorisasi banyak angka di rentang: precompute SPF via linear sieve → O(log n) per faktorisasi.
  • Untuk n sangat besar (> 10¹⁸): gunakan Pollard’s rho (probabilistik O(n^(1/4))), atau algoritma sub-eksponensial (quadratic sieve, GNFS).