Lanjut60 XPUnit 8: Matematika dan Bilangan, soal 13 dari 13
Banyak Bilangan Prima
Hitung banyaknya bilangan prima sampai dua juta dengan cepat.
Memeriksa jutaan bilangan satu per satu terlalu lambat. Eratosthenes, ilmuwan Yunani kuno, punya cara yang jauh lebih cerdik: coret semua kelipatan bilangan prima, dan yang tersisa pasti prima.
Masukan
Satu bilangan bulat N dari 1 sampai 2000000.
Keluaran
Banyaknya bilangan prima yang kurang dari atau sama dengan N.
Contoh masukan dan keluaran
Contoh 1
Masukan
30
Keluaran
10
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Siapkan daftar penanda sepanjang N + 1 yang semuanya bernilai benar, lalu tandai 0 dan 1 sebagai bukan prima.
Petunjuk 2
Untuk setiap i yang masih bertanda prima, coret semua kelipatannya mulai dari i * i. Cukup lakukan untuk i sampai akar N.