Bilangan Prima

Bilangan prima adalah atom dalam aritmetika bilangan bulat — setiap bilangan bulat positif lebih dari 1 dapat diuraikan menjadi produk bilangan prima (Fundamental Theorem of Arithmetic). Banyak algoritma modern (RSA, Diffie–Hellman, hashing universal) bergantung pada keberadaan dan distribusi bilangan prima. Pada Chapter ini kita akan mendefinisikan prima secara formal, lalu membangun primality test dari yang paling naif hingga varian yang memanfaatkan pola 6k ± 1.

Definisi Bilangan Prima #

Aturan #

Bilangan bulat n > 1 disebut prima bila satu-satunya pembagi positifnya adalah 1 dan n itu sendiri. Bila n > 1 bukan prima, n disebut komposit.

• 1 tidak prima (konvensi modern; membuat Fundamental Theorem of Arithmetic unik).
• 2 adalah satu-satunya prima genap. Semua prima lain ganjil.
• Deret prima dimulai: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ....

Mekanisme: Mengapa Cek Cukup Sampai √n #

Misalkan n komposit: n = a · b dengan 1 < a ≤ b < n. Maka a² ≤ a · b = n, sehingga a ≤ √n. Jadi, bila n memiliki pembagi non-trivial, setidaknya salah satu pembaginya ≤ √n. Cukup uji kandidat pembagi d mulai 2 hingga ⌊√n⌋ — bila tidak ada yang habis membagi, n prima.

Primality Test: Trial Division Naif #

Aturan #

Versi naif: uji setiap d dari 2 hingga n-1. Kompleksitas O(n). Cukup untuk n kecil, tetapi sangat lambat untuk n ≈ 10⁹.

Kode: Versi Naif vs Optimized √n #

#include <iostream>

// Naive trial division: cek semua kandidat pembagi 2..n-1
bool isPrimeNaive(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i < n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

// Optimized: cek hingga sqrt(n)
bool isPrimeSqrt(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

// Lebih optimal: 2, 3, lalu pola 6k+/-1
bool isPrimeOpt(long long n) {
    if (n < 2) return false;
    if (n < 4) return true;          // 2, 3
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (long long i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

int main() {
    std::cout << "Bilangan prima 1..30: ";
    for (int n = 1; n <= 30; ++n) {
        if (isPrimeOpt(n)) std::cout << n << ' ';
    }
    std::cout << '\n';

    long long tests[] = {1, 2, 17, 25, 97, 100, 1000003LL, 1000000007LL};
    for (long long x : tests) {
        std::cout << "isPrimeOpt(" << x << ") = "
                  << (isPrimeOpt(x) ? "true" : "false") << '\n';
    }

    // Sanity check: ketiga versi harus sepakat untuk 1..1000
    bool ok = true;
    for (int n = 0; n <= 1000; ++n) {
        if (isPrimeNaive(n) != isPrimeOpt(n) || isPrimeSqrt(n) != isPrimeOpt(n)) {
            ok = false;
            std::cerr << "Mismatch at n=" << n << '\n';
        }
    }
    std::cout << "Konsistensi 1..1000: " << (ok ? "OK" : "FAIL") << '\n';
    return 0;
}

Output yang Dihasilkan:

Bilangan prima 1..30: 2 3 5 7 11 13 17 19 23 29 
isPrimeOpt(1) = false
isPrimeOpt(2) = true
isPrimeOpt(17) = true
isPrimeOpt(25) = false
isPrimeOpt(97) = true
isPrimeOpt(100) = false
isPrimeOpt(1000003) = true
isPrimeOpt(1000000007) = true
Konsistensi 1..1000: OK

1. Baris if (n < 2) return false;: konvensi modern — 0 dan 1 bukan prima.
2. Baris for (long long i = 2; i * i <= n; ++i): loop hanya sampai ⌊√n⌋. Memakai i * i <= n (alih-alih i <= sqrt(n)) menghindari floating point dan presisi yang rapuh.
3. Baris if (n % 2 == 0 || n % 3 == 0) return false;: eliminasi cepat — kelipatan 2 atau 3 bukan prima (kecuali 2 dan 3 sendiri yang sudah ditangani baris sebelumnya).
4. Baris for (long long i = 5; i * i <= n; i += 6): setelah 2 dan 3, semua prima berikutnya berbentuk 6k ± 1 (karena 6k, 6k+2, 6k+3, 6k+4 habis dibagi 2 atau 3). Loop melompati 6 setiap iterasi, menguji dua kandidat: i (=6k-1) dan i+2 (=6k+1).
5. Hasil isPrimeOpt(1000003) = true: 1'000'003 prima (periksa: tidak ada pembagi ganjil ≤ √1000003 ≈ 1000).
6. Hasil isPrimeOpt(1000000007) = true: 10⁹+7 adalah prima — pilihan populer sebagai modulus di kompetisi algoritma.
7. Baris sanity check: memastikan ketiga implementasi sepakat pada 0..1000. OK menandakan tidak ada perbedaan hasil.

Optimasi Lanjutan: Pola 6k ± 1 #

Aturan #

Setiap bilangan bulat dapat ditulis dalam salah satu bentuk 6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5. Dari enam bentuk ini, hanya 6k+1 dan 6k+5 (= 6k-1) yang tidak otomatis kelipatan 2 atau 3. Maka setelah memeriksa 2 dan 3, kita hanya perlu menguji pembagi berbentuk 6k ± 1. Ini memangkas ~⅔ dari iterasi dibanding loop naif.

Mekanisme: Mengapa 6k ± 1, Bukan 30k ± {1,7,11,13,…}? #

Kita bisa melangkah lebih jauh dengan 30k ± {1,7,11,13,17,19,23,29} (mengeliminasi kelipatan 2, 3, 5) — tetapi kompleksitas asimptotik tetap O(√n). Peningkatan konstanta faktor menjadi semakin kecil, sarta kode makin rumit. Pola 6k ± 1 adalah sweet spot antara kesederhanaan dan kecepatan.

Kompleksitas dan Perbandingan #

Aplikasi #

• RSA cryptography: kunci publik n = p · q dengan p, q prima besar (2048-bit). Primality test cepat esensial untuk generate key.
• Hashing universal: pilih prima besar p sebagai modulus, lalu h(x) = (a · x + b) mod p.
• Number theory: banyak teorema (Fermat, Wilson) hanya berlaku untuk prima.
• Modular inverse via Fermat: lihat Chapter Modular Inverse — bergantung pada modulus prima.

Ringkasan #

• Definisi: n > 1 prima iff pembagi positif hanya 1 dan n.
• Trial division: cek pembagi d dari 2 hingga ⌊√n⌋. Kompleksitas O(√n).
• Optimasi 6k ± 1: setelah cek 2 dan 3, hanya uji d berbentuk 6k ± 1 — memangkas ~⅔ iterasi.
• Implementasi i * i <= n (bukan i <= sqrt(n)) menghindari floating point.
• Untuk banyak query, gunakan Sieve; untuk n sangat besar, gunakan Miller–Rabin.