Cara Mencari bilangan Prima Dengan Algoritma Sieve of Eratosthenes

Seperti yang kita ketahui (buat yang udah pada tau) bahwa bilangan prima adalah bilangan (>1) yang hanya habis dibagi oleh bilangan 1 dan bilangan itu sendiri. sebenarnya ada banyak cara untuk mencari bilangan prima. salah satu adalah memastikan suatu bilangan (n>1) tidak habis dibagi bilangan bulat mulai dari 2 sampai round(sqrt(n)). Namun cara ini cukup memakan waktu yg agak lama. Untuk mencari bilangan prima dengan cepat , kita dapat menggunakan Algoritma Sieve of Eratosthenes. algo Eratosthenes ini cepat karena dia mencari bilangan prima dengan sebelumnya mencoret bilangan-bilangan yang bukan prima dan kelipatannya.

Langkah-langkah :

apabila kita ingin mencari bilangan prima dari 1 sampai n :

1. Tulis semua bilangan, mulai dari 1 sampai n. Misalkan ini adalah daftar A.
2. Buat suatu daftar yang masih kosong, sebut saja daftar B.
3. Coret bilangan 1 dari daftar A.
4. Lalu tulis 2 pada daftar B. Lalu coret 2 dan semua kelipatannya dari daftar A.
5. Bilangan pertama yang belum tercoret dari daftar A (misalnya 3) adalah bilangan prima. Tulis bilangan ini di daftar B, lalu coret bilangan ini dan semua kelipatannya dari daftar A.
6. Ulangi langkah 4 sampai semua bilangan di daftar A sudah tercoret.

Setelah selesai, semua bilangan di daftar B adalah bilangan prima.

ini adalah contoh source codenya :

Semoga Berguna