Latihan Soal OSN Informatika: Sieve of Eratosthenes
Oleh Daniel Wirajaya (website)
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 buah bilangan bulat: hingga .
Batasan
Masukan
Masukan diberikan dalam format berikut:
n
A₁ ... Aₙ
Keluaran
Keluaran berbentuk buah baris dalam format
Aᵢ = Xᵢ + Yᵢ
di mana dan adalah bilangan prima.
Angka dan operator dipisahkan dengan spasi. Jika ada lebih dari satu pasang bilangan prima yang jumlahnya sama dengan , pilihlah pasangan di mana memiliki nilai terbesar.
Jika tidak ada dua bilangan prima
yang jumlahnya sama dengan ,
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.
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
sampain
. - Angka pertama, yaitu
2
adalah bilangan prima. Coret semua angka kelipatan2
karena pasti bulan merupakan bilangan prima. - Angka berikutnya yang belum dicoret, yaitu
3
, adalah bilangan prima. Coret semua angka kelipatan3
. - Angka berikutnya yang belum dicoret, yaitu
5
, adalah bilangan prima. Coret semua angka kelipatan5
. - Lanjutkan proses ini sampai dengan .
Sebagai contoh, mari kita ambil contoh penggunaan Sieve of Eratosthenes ini untuk angka sampai dengan 20.
Langkah 1. Buat baris angka dari 2
sampai 20
.
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 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 ,
bukannya dari , karena kelipatan
yang lebih kecil dari
sebetulnya sudah dicoret dalam iterasi sebelumnya. Contohnya dalam Langkah 4
di atas, kelipatan
5
yang lebih kecil dari25
sudah dicoret semuanya, sehingga ketika ingin mencoret semua angka kelipatan5
, kita bisa memulainya dari angka25
. 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 kita akan menghitung selisihnya
dengan bilangan prima () yang ada di vector tersebut,
satu per satu mulai dari yang terkecil. Jika selisihnya ()
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
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.