Sieve of Eratosthenes

Saat kita perlu mengetahui apakah setiap bilangan di rentang [1, N] prima atau tidak (misalnya untuk memproses banyak query), memanggil primality test satu per satu membutuhkan waktu O(N · √N) — terlalu lambat. Sieve of Eratosthenes menyelesaikan masalah ini dengan menandai bilangan komposit secara bulk, mencapai O(N log log N). Chapter ini membahas implementasi klasik, optimasi memori dengan bitset, lalu dua varian penting: linear sieve (O(N)) dan segmented sieve (untuk N sangat besar).

Ide Dasar Sieve #

Aturan #

Untuk menemukan semua prima ≤ N:

1. Buat array is_composite[0..N] semula false.
2. Tandai is_composite[0] = is_composite[1] = true (0 dan 1 bukan prima).
3. Untuk setiap p = 2, 3, 4, ... hingga p² ≤ N:
   • Bila p belum ditandai (prima), tandai semua kelipatan p², 2p, 3p, ... sebagai komposit.
4. Bilangan yang tidak ditandai adalah prima.

Mekanisme: Mengapa Mulai dari p²? #

Saat kita memproses prima p, kelipatan 2p, 3p, ..., (p-1)·p sudah ditandai sebelumnya oleh prima lebih kecil (yaitu prima pembagi 2, 3, ..., p-1). Kelipatan pertama yang belum ditandai adalah p · p = p². Inilah alasan loop batin dimulai dari p² — menghindari pekerjaan redundan dan menjaga kompleksitas O(N log log N).

Implementasi Standar #

Kode: Sieve of Eratosthenes #

#include <iostream>
#include <vector>

// Sieve of Eratosthenes: kembalikan daftar prima <= n
std::vector<int> sieve(int n) {
    if (n < 2) return {};
    std::vector<bool> is_composite(n + 1, false);
    is_composite[0] = is_composite[1] = true;
    for (int p = 2; (long long)p * p <= n; ++p) {
        if (!is_composite[p]) {
            // Mulai dari p*p: kelipatan lebih kecil sudah ditandai oleh prima lebih awal
            for (int m = p * p; m <= n; m += p) {
                is_composite[m] = true;
            }
        }
    }
    std::vector<int> primes;
    for (int i = 2; i <= n; ++i) {
        if (!is_composite[i]) primes.push_back(i);
    }
    return primes;
}

int main() {
    int n = 50;
    auto primes = sieve(n);
    std::cout << "Jumlah prima <= " << n << ": " << primes.size() << '\n';
    std::cout << "Daftar: ";
    for (int p : primes) std::cout << p << ' ';
    std::cout << '\n';

    // Verifikasi: pi(10^6) = 78498 (known)
    auto big = sieve(1'000'000);
    std::cout << "pi(10^6) = " << big.size() << " (expected 78498)\n";

    // Demo iterasi: untuk n = 30, tampilkan status marking setelah setiap prima
    int demo_n = 30;
    std::vector<bool> comp(demo_n + 1, false);
    comp[0] = comp[1] = true;
    for (int p = 2; p * p <= demo_n; ++p) {
        if (!comp[p]) {
            for (int m = p * p; m <= demo_n; m += p) comp[m] = true;
            std::cout << "Setelah mark kelipatan " << p << ": ";
            for (int i = 2; i <= demo_n; ++i) {
                if (comp[i]) std::cout << "X ";
                else std::cout << i << ' ';
            }
            std::cout << '\n';
        }
    }
    return 0;
}

Output yang Dihasilkan:

Jumlah prima <= 50: 15
Daftar: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 
pi(10^6) = 78498 (expected 78498)
Setelah mark kelipatan 2: 2 3 X 5 X 7 X 9 X 11 X 13 X 15 X 17 X 19 X 21 X 23 X 25 X 27 X 29 X 
Setelah mark kelipatan 3: 2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X 25 X X X 29 X 
Setelah mark kelipatan 5: 2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X X X X X 29 X 

1. Baris std::vector<bool> is_composite(n + 1, false);: C++ mengkhususkan vector<bool> menjadi packed bit-array (1 bit per elemen) — hemat memori ~8× dibanding vector<char>. Untuk N = 10⁸, memori turun dari 100 MB menjadi 12.5 MB.
2. Baris for (int p = 2; (long long)p * p <= n; ++p): cast p ke long long sebelum perkalian p * p agar tidak overflow saat p mendekati √INT_MAX. Tanpa cast, 46341 * 46341 overflow int.
3. Baris if (!is_composite[p]): lewati p yang sudah ditandai — p bukan prima sehingga kelipatannya sudah ditandai oleh prima pembaginya.
4. Baris for (int m = p * p; m <= n; m += p): tandai p², p²+p, p²+2p, ... sebagai komposit. Mulai dari p² (bukan 2p) — lihat mekanisme di atas.
5. Hasil pi(10^6) = 78498: konstanta terkenal dari prime counting function. Implementasi benar.
6. Demo iterasi: setelah memproses prima p = 2, semua genap menjadi X. Setelah p = 3, semua kelipatan 3 (yang belum X) ikut ditandai. Setelah p = 5, hanya 25 yang baru ditandai (karena 10, 15, 20 sudah X dari kelipatan 2). Bilangan tersisa yang tidak X adalah prima.

Optimasi Memori dengan std::bitset #

Aturan #

std::bitset<N> adalah array bit statis ukuran compile-time. Lebih cepat dari vector<bool> karena ukuran tetap memungkinkan compiler mengoptimalkan akses bit. Untuk N = 10⁷, bitset<10'000'000> hanya butuh ~1.25 MB.

Linear Sieve: O(N) #

Aturan #

Setiap bilangan komposit c ditandai tepat satu kali oleh faktor primanya yang terkecil. Inilah trik linear sieve — kompleksitas turun dari O(N log log N) menjadi O(N).

Mekanisme: Penandaan Minimal Prime Factor #

Untuk setiap i = 2, 3, ..., N:

• Bila i belum ditandai, masukkan ke daftar prima.
• Untuk setiap prima p di daftar (dari kecil ke besar):
  • Bila p > N / i, break (i · p akan > N).
  • Tandai i · p sebagai komposit dengan smallest_prime[i·p] = p.
  • Bila i % p == 0, break ( agar i · p ditandai oleh p, bukan prima yang lebih besar — inilah yang menjamin setiap komposit ditandai tepat sekali ).

Kode: Linear Sieve #

#include <iostream>
#include <vector>

int main() {
    const int N = 30;
    std::vector<int> primes;
    std::vector<bool> comp(N + 1, false);

    for (int i = 2; i <= N; ++i) {
        if (!comp[i]) primes.push_back(i);
        for (int p : primes) {
            long long m = (long long)i * p;
            if (m > N) break;
            comp[m] = true;
            if (i % p == 0) break;   // kunci linearitas
        }
    }

    std::cout << "Prima <= " << N << " (" << primes.size() << "): ";
    for (int p : primes) std::cout << p << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

Prima <= 30 (10): 2 3 5 7 11 13 17 19 23 29 

1. Baris if (!comp[i]) primes.push_back(i);: i belum ditandai oleh prima manapun → prima.
2. Baris for (int p : primes): iterasi prima dari kecil ke besar.
3. Baris if (m > N) break;: i · p melebihi N — tidak ada gunanya menandai.
4. Baris comp[m] = true;: tandai i · p sebagai komposit.
5. Baris if (i % p == 0) break;: kunci linearitas. Bila p membagi i, maka i · p' untuk prima p' > p akan ditandai nanti oleh i' = i · p / p' = (i/p) · p' (yang memiliki faktor prima terkecil p'), bukan p. Setiap komposit ditandai tepat sekali oleh faktor primanya yang terkecil.

Segmented Sieve untuk N Besar #

Aturan #

Saat N terlalu besar untuk array O(N) (misal N = 10¹² tetapi kita hanya butuh prima di [L, R] dengan R - L ≤ 10⁷), gunakan segmented sieve:

1. Sieve prima hingga √R dengan sieve klasik (kecil).
2. Buat array block[R-L+1] bertanda “belum komposit”.
3. Untuk setiap prima p ≤ √R, hitung start = max(p², ⌈L/p⌉ · p), lalu tandai kelipatan start, start+p, ... ≤ R sebagai komposit.

Kompleksitas dan Perbandingan #

Aplikasi #

• Primality precheck: bangun sieve ≤ √N_max sekali, lalu primality test cepat bagi n ≤ N_max.
• Prime counting function π(N): hitung berapa banyak prima ≤ N.
• Faktorisasi cepat: setelah sieve linear menyimpan smallest_prime[i], faktorisasi n adalah n → n/sp[n] → ... → 1 dalam O(log n). Lihat Chapter Faktorisasi Prima .
• Möbius function, Euler’s totient via sieve linear — bisa dihitung bersamaan dalam O(N).

Ringkasan #

• Sieve klasik: tandai kelipatan p², 2p, ... untuk setiap prima p ≤ √N. Kompleksitas O(N log log N), memori O(N) bit.
• Mulai marking dari p² (bukan 2p) — kelipatan 2p, ..., (p-1)p sudah ditandai oleh prima lebih kecil.
• std::vector<bool> dan std::bitset memakai 1 bit per elemen — hemat memori.
• Linear sieve: O(N) dengan break pada i % p == 0 — setiap komposit ditandai tepat sekali.
• Segmented sieve: untuk [L, R] di N besar, gunakan sieve ≤ √R lalu tandai di blok [L, R].