Senin, 22 November 2010

Sieve Of Eratosthenes

    Sieve of Erastosthenes adalah suatu Number Theoritic Algorithm khusus untuk mencari bilangan prima.
    Algoritma ini merupakan yang tercepat di bidangnya, karena menggunakan list data untuk menyimpan bilangan prima yang sudah di temukan dan menghapus bilangan kelipatan prima tersebut.


Contoh : 3 adalah bilangan prima, kelipatan 3 pasti bukan bilangan prima, jangan tanya kenapa !! :D


dah ngerti kan ???
ini ada contoh source code yang saya buat :D
#include <iostream>
#include <math.h>

typedef long long LL;

using namespace std;

LL N;
bool Prima[1000000000];

int main()
{
    cout<<"Masukan angka maximal bilangan prima yang anda inginkan = ";cin>>N;
    for(LL i=0;i<N;i++)   // semua di set true dulu.
        Prima[i] = true;
    Prima[0] = false;
    Prima[1] = false;
    cout<<"Bilangan Prima dari 1 - "<<N<<" adalah : "<<endl;

    for(LL i=2*2;i<N;i+=2) //bilangan prima pasti bukan bilangan genap,
        Prima[i] = false;  //kecuali 2. Jadi kelpatan 2 di buang dulu.

    for(LL i=3;i<sqrt(N);i+=2)  //disini langsung mencari bilangan ganjil saja.
        if(Prima[i])
            for(LL j=i*i;j<N;j+=i)
                Prima[j] = false;
    for(LL i=2;i<N;i++)
        if(Prima[i])
            cout<<i<<endl;
    return 0;
}

Tidak ada komentar:

Posting Komentar