Generate bilangan prima dengan algoritma Sieve of Eratosthenes

Bilangan prima adalah bilangan (>1) yang hanya habis dibagi oleh bilangan 1 dan bilangan itu sendiri, yakni: 2, 3, 5, 7, 11, 13, 17, ....

Untuk generate bilangan prima secara cepat, dapat dilakukan dengan menggunakan algo sieve of Eratosthenes, algo Eratosthenes ini cepet karena dia mengenerate bilangan prima dengan sebelumnya mencoret bilangan-bilangan yang bukan prima dan kelipatannya.

Untuk ilustrasi lebih mendatail mengenai cara kerjanya dapat dilihat lebih lengkap di http://en.wikipedia.org/wiki/Sieve_of_eratosthenes

Dibawah ini code generate bilangan prima yang < 10000000 dengan Sieve of Eratosthenes yang telah dimodifikasi, supaya lebih cepat.
Cara mempercepat:
- Coret semua yang habis dibagi 2 dengan operasi modulo
- Cek hanya untuk setengah dari kuadrat jumlah bilangan (jika akan mengenerate 10000 bilangan prima, tidak melakukan pemeriksaan dari 1-10000, tapi hanya dari 1-100 saja, karena jika bilangan awalnya bukan prima, maka kuadratnya juga pasti bukan prima)

/* Sieve of Eratosthenes + pruning++ , 3 times faster than Sieve of Erastosthenes*/
/* Displaying prime numbers lower than 10000000 */
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<math.h>
#define max1 10000000

long i,n,a,c,j; bool flag[max1];

int main()
{
    time_t begin = clock();
    c = sqrt(max1);
    flag[2] = true;
    for(i=3; i<=max1; i++) if(i%2==0) flag[i] = false; else flag[i] = true;
    for(i=2; i<=c; i++)
        if(flag[i]==true)
            for(j=i*i; j<max1; j+=i*2)
                flag[j] = false;
    for(i=2; i<=max1; i++)
        if(flag[i]==true) printf ("%ld\n", i);

    printf("%lf secs", double(clock()-begin) / CLOCKS_PER_SEC);

    return 0;
}

Last edited by StevenLuck (2009-07-22 16:23:46)