Latihan Soal OSN Informatika: Sieve of Eratosthenes

Oleh Daniel Wirajaya (website)

Co-founder, Acutis Academy; Director, QuBisa. Pakar e-learning dengan pengalaman industri lebih dari 20 tahun.

Soal

Pak Dengklek penasaran dengan Konjektur Goldbach. Sudah ratusan tahun dan banyak Matematikawan terkenal mencoba membuktikannya, tetapi sejauh ini belum ada yang berhasil.

Konjektur Goldbach berbunyi: Setiap bilangan genap yang lebih besar dari 4 merupakan hasil penjumlahan dari 2 bilangan prima. Contohnya: 8 = 3 + 5, di mana 3 dan 5 adalah bilangan prima. 12 = 5 + 7, 20 = 3 + 17 = 7 + 13, dst.

Pak Dengklek ingin membuktikan konjektur ini untuk $n$ buah bilangan bulat: $A_{1}$ hingga $A_{n}$ .

Batasan

$1 \leq n \leq 100$
$6 \leq A_{i} \leq 1 000 000$

Masukan

Masukan diberikan dalam format berikut:

n
A₁ ... Aₙ

Keluaran

Keluaran berbentuk $n$ buah baris dalam format

Aᵢ = Xᵢ + Yᵢ

di mana $X_{i}$ dan $Y_{i}$ adalah bilangan prima.

Angka dan operator dipisahkan dengan spasi. Jika ada lebih dari satu pasang bilangan prima yang jumlahnya sama dengan $A_{i}$ , pilihlah pasangan di mana $Y_{i} - X_{i}$ memiliki nilai terbesar.

Jika tidak ada dua bilangan prima yang jumlahnya sama dengan $A_{i}$ , tuliskan Konjektur Goldbach salah.

Contoh Masukan

2
12 20

Contoh Keluaran

12 = 5 + 7
20 = 3 + 17

Pembahasan

Untuk menjawab soal ini, kita memerlukan sederetan angka bilangan prima yang dapat kita peroleh secara efisien dengan menggunakan Sieve of Eratosthenes.

Reruntuhan Kota Tua Kirene, Cyrenaica, Libya: kampung halaman Eratosthenes. (Public Domain)

Sieve of Eratosthenes adalah salah satu algoritma yang paling efisien untuk mendapatkan semua bilangan prima yang lebih kecil dari angka tertentu. Algoritma ini dirancang oleh Eratosthenes dari Kirene sekitar 3 abad SM, dan tetap digunakan sampai saat ini.

Cara Kerja Sieve of Eratosthenes

Algoritma ini secara otomatis “menyaring” angka-angka komposit (angka yang bukan bilangan prima), sehingga hanya angka-angka prima yang tersisa.

Misalnya kita ingin mendapatkan semua bilangan prima yang lebih kecil dari angka tertentu, misalnya n. Maka langkah-langkahnya ada seperti ini:

Buat barisan angka dari 2 sampai n.
Angka pertama, yaitu 2 adalah bilangan prima. Coret semua angka kelipatan 2 karena pasti bulan merupakan bilangan prima.
Angka berikutnya yang belum dicoret, yaitu 3, adalah bilangan prima. Coret semua angka kelipatan 3.
Angka berikutnya yang belum dicoret, yaitu 5, adalah bilangan prima. Coret semua angka kelipatan 5.
Lanjutkan proses ini sampai dengan $\sqrt{n}$ .

Sebagai contoh, mari kita ambil contoh penggunaan Sieve of Eratosthenes ini untuk angka sampai dengan 20.

Langkah 1. Buat baris angka dari 2 sampai 30.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Langkah 2. 2 adalah bilangan prima. Coret semua kelipatan 2.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Langkah 3. 3 adalah bilangan prima. Coret semua kelipatan 3.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Langkah 4. 5 adalah bilangan prima. Coret semua kelipatan 5 (yang sudah dicoret semua di iterasi sebelumnya).

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Karena 5 sudah lebih besar dari $\sqrt{20}$ maka iterasi bisa dihentikan sampai di sini, dan kita sudah mendapatkan barisan bilangan prima yang kita inginkan, yaitu

2 3 5 7 11 13 17 19

Optimasi terhadap Sieve of Eratosthenes

Beberapa optimasi dapat dilakukkan terhadap algoritma Sieve of Eratosthenes yang dijabarkan di atas:

Mulai setiap iterasi dari $p^{2}$ , bukannya dari $2 p$ , karena kelipatan $p$ yang lebih kecil dari $p^{2}$ sebetulnya sudah dicoret dalam iterasi sebelumnya. Contohnya dalam Langkah 4 di atas, kelipatan 5 yang lebih kecil dari 25 sudah dicoret semuanya, sehingga ketika ingin mencoret semua angka kelipatan 5, kita bisa memulainya dari angka 25. Kode program implementasi Sieve of Eratosthenes yang diberikan di bawah ini melakukan optimasi ini.
Karena semua bilangan bulat yang lebih besar dari 2 merupakan bilangan komposit, maka kita sebetulnya hanya perlu menyaring bilangan ganjil saja.

Jawaban Soal

Dengan menggunakan Sieve of Eratosthenes, kita dapat membuat sebuah larik (array) yang berisi semua bilangan prima dengan nilai di bawah 1 000 000. Untuk ini kita dapat memanfaatkan vector, yang merupakan bagian dari Standard Template Library (STL).

Lalu untuk setiap $A_{i}$ kita akan menghitung selisihnya dengan bilangan prima ( $X_{j}$ ) yang ada di vector tersebut, satu per satu mulai dari yang terkecil. Jika selisihnya ( $A_{i} - X_{j}$ ) merupakan bilangan prima juga, berarti kita sudah menemukan jawaban yang kita inginkan. Tetapi jika selisihnya itu bukan merupakan bilangan prima, maka kita akan melanjutkan ke bilangan prima berikutnya yang ada di vector. Jika sampai di akhir vector kita tidak menemukan $A_{i} - X_{j}$ yang merupakan bilangan prima, maka cetaklah output Konjektur Goldbach salah.

Implementasi

Berikut adalah kode program dalam C++ untuk menjawab soal di atas.

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

vector<bool> sieveOfEratosthenes(int n)
{
    // Buat vector dengan n + 1 elemen. Semua elemen bernilai true
    vector<bool> prime(n + 1, true);

    // 0 dan 1 bukan bilangan prima
    prime[0] = prime[1] = false;

    for (int p = 2; p * p <= n; ++p)
    {
        // Jika p adalah bilangan prima ...
        if (prime[p])
        {
            // ... maka semua kelipatan p bukanlah bilangan prima.
            // Mulai dari p * p, karena semua kelipatan p yang lebih kecil
            //    dari p * p sudah ditandai sebagai bukan bilangan prima
            //    pada iterasi sebelumnya.
            for (int i = p * p; i <= n; i += p)
            {
                prime[i] = false;
            }
        }
    }

    return prime;
}

int main()
{
    int N;
    vector<int> A;

    // Masukkan semua input ke dalam variabel N dan A
    //   sesuai format pada soal.
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int a;
        cin >> a;
        A.push_back(a);
    }

    // Buat sieve dengan 1 000 000 elemen
    vector<bool> sieve = sieveOfEratosthenes(1'000'000);

    // Berdasarkan sieve, buat vector yang berisi
    //    semua angka prima mulai dari 1 sampai 1 000 000
    vector<int> primes;
    for (int p = 2; p <= sieve.size(); ++p)
    {
        // Jika p adalah bilangan prima, masukkan pada vector primes.
        if (sieve[p])
        {
            primes.push_back(p);
        }
    }

    for (int n = 0; n < N; n++)
    {
        // Untuk setiap bilangan yang ditanyakan,
        //     simpan bilangan tersebut dalam variabel num.
        int num = A[n];

        // Gunakan flag untuk menandai apakah jawaban
        //     sudah ditemukan atau belum.
        bool ok = false;

        // Lakukan iterasi terhadap bilangan prima
        //     mulai dari yang terkecil.
        for (int i = 0; i <= primes.size(); i++)
        {
            if (primes[i] * 2 > num)
                break;

            // Untuk setiap bilangan prima primes[i],
            //    cek apakah num - primes[i] merupakan bilangan prima juga.
            //    Jika ya, maka kita sudah menemukan pasangan bilangan yang
            //    dicari, yaitu primes[i] dan (num - primes[i]).
            if (sieve[num - primes[i]])
            {
                ok = true;
                cout << num << " = " << primes[i] << " + " << (num - primes[i]) << endl;
                break;
            }
        }
        if (!ok)
        {
            cout << "Konjektur Goldbach salah" << endl;
        }
    }
    return 0;
}

Kesimpulan

Sieve of Eratosthenes sampai saat ini masih banyak digunakan, terutama dalam bidang Kriptografi, dan riset Matematika. Selain itu, algoritma ini juga sangat bermanfaat dalam kompetisi pemrograman, seperti OSN Informatika, untuk menjawab soal-soal yang berkaitan dengan bilangan prima, sehingga perlu dikuasai dengan baik.