Bilangan Prima adalah bilangan bulat positif lebih besar dari satu yang memiliki tepat hanya dua factor,yaitu bilangan 1 (satu) dan bilangan itu sendiri.
Deret bilangan Prima
Dalam sejarah perkembangan bilangan prima telah ditemukan beberapa algoritma dalam pencarian deret bilangan prima, seperti Steve of Eratosthhenes dan Steve of Afkin.
Algoritma yang paling sedehana dan paling tua mungkin adalah Steve of Eratosthenes, Algoritma ini ditemukan oleh matematika kawan Yunani kuno, Eratosthenes. Algoritma Steve of Eratosthenes adalah:
1) Pertama-tama, tuliskan daftar bilangan dari 2 sampai batas bilangan yang akan dicari.
2) Kemudian, tandai bilangan didalam daftar yang merupakan kelipatan 2, dengan meninggalkan bilangan 2 tetap tidak ditandai.
3) Lanjutkan ke bilangan berikutnya (dalam tahap ini adalah bilangan 3), dan tandai setiap kelipatan 3 dengan tetap meninggalkan bilangan 3 tidak ditandai.
4) Lanjutkan ke bilangan berikutnya. Bila bilangan berikut tersebut telah ditandai, lanjutkan ke bilangan berikutnya.
5) Lanjutkan langkah penandaan seperti di atas sampai batas bilangan.
Bilangan yang belum ditandai adalah merupakan bilangan prima.
Algoritma ini menggunakan fakta bahwa jika sebuah bilangan adalah prima, maka kelipatan dari bilangan tersebut pastilah bukan prima.
Algoritma ini mempunyai komplektifitas algoritma O( N2 ) dengan N adalah batas atas bilangan.
Algoritma
FLOWCHART
Program Dalam DEV C++
0 komentar:
Posting Komentar