[Prima] Sieve of Sundaram

Sieve of Sundaram merupakan prime generator tercanggih yang pernah saya temui, karena kecepatannya, mudah dipahami dan kemudahannya dalam implementasi ke bahasa pemrograman, ditemukan pada tahun 1934 oleh Sundaram. Ok sekarang kita coba gimana sih caranya menggunakan algoritma ini?



1. coba kita buat list dari semua bilangan bulat positif (kali ini saya coba sampai 25)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

2. lalu kita coret yang termasuk dalam persamaan i + j + 2 * i * j;

Kita anggap angka 25 yang diatas adalah n, maka kita harus mencari nilai yang memenuhi :
 i + j + 2 * i * j <= n, sehingga  i + j + 2 * i * j <= 25. Lalu kita coba dari i = 1 dan j = 1.

i = 1 dan j = 1 maka = 1 + 1 + 2 = 4 // 1 + 1 + 2 * 1 * 1 = 4
i = 1 dan j = 2 maka = 1 + 2 + 4 = 7
i = 1 dan j = 3 maka = 1 + 3 + 6 = 10
i = 1 dan j = 4 maka = 1 + 4 + 8 = 13
i = 1 dan j = 4 maka = 1 + 5 + 10 = 16
i = 1 dan j = 5 maka = 1 + 6 + 12 = 19
i = 1 dan j = 6 maka = 1 + 7 + 14 = 22
i = 1 dan j = 7 maka = 1 + 8 + 16 = 25 //stop karena kan list kita ampe 25. lalu masuk ke i = 2;

kita mulai dari j = 2 kenapa? karena kalau kita mulai dari j = 1 maka itu sama saja dengan i =1 dan j = 2 jadi lebih baik kita mulai dari i.

i = 2 dan j = 2 maka = 2 + 2 + 8 = 12
i = 2 dan j = 3 maka = 2 + 3 + 12 = 17
i = 2 dan j = 4 maka = 2 + 4 + 16 = 22
i = 2 dan j = 5 maka = 2 + 5 + 20 = 27 //stop udah lewat.

i = 3 dan j = 3 maka = 3 + 3 + 18 = 24 //stop.

3. semua angka yang muncul tadi kita coret.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

menurut sundaram angka yang tidak dicoret tersebut kalau kita (2 * bilangan tidak dicoret  + 1) adalah bilangan prima mari kita coba :

2 * 1 + 1 = 3
2 * 2 + 1 = 5
2 * 3 + 1 = 7
2 * 5 + 1 = 11
2 * 6 + 1 = 13
2 * 8 + 1 = 17
2 * 9 + 1 = 19
2 * 11 + 1 = 23
2 * 14 + 1 = 29
2 * 15 + 1 = 31
2 * 18 + 1 = 37
2 * 20 + 1 = 41
2 * 21 + 1 = 43
2 * 23 + 1 = 47

so thats it sieve of sundaram.. semoga membantu :)

ini gambarnya kalau merasa kesulitan

Good Luck!