Mencari bilangan prima dengan Algoritma Eratosthenes ~ Pemrograman dan Teknologi

Sebelum membaca semua tulisan-tulisan saya setelah ini kalian sebaiknya sudah yakin bahwa kalian sudah memahami dasar pemrograman. Untuk teorinya dan penerarapnnya dalam matematika, silakan baca di blog saya yang lain. Di sini saya cuma akan berbagi kode programnya.

Berikut ini saya akan membahas tentang cara mencari bilangan prima dengan C++. Untuk mencari bilangan prima kita bisa mencarinya dengan algoritma Eratosthenes. Berikut ini penerapan Algoritma Eratosthenes untuk mencari bilangan prima dari 1 sampai dengan 100 menggunakan Array yang ditulis dalam bahasa C++.

#include <iostream>

using namespace std;

int main(){
int i, j, n;
char a[101];
    i=0;n=100;
    while(i<=100){
        a[i]=0;
        i++;
    }

    i=2;
    while((j=i*i)<n){
        if(a[i]==0){
            cout << i << " " ;
            while(j<=n){
                a[j]=1;
                j+=i;
            }
        }
        i++;
    }

    while(i<n){
        if(a[i]==0){
            cout << i << " " ;
        }
        i++;
    }

    return 0;
}

Kode program di atas menggunakan aray sebanyak jumlah data ditambah dengan satu "n+1". Kalian bisa mengubahnya seperti di bawah ini jika ingin menggunakan array dinamis dan mengubah nilai maksimalnya.

#include <iostream>
#include <stdlib.h>

using namespace std;

int main(){
int i, j, n;
char *a;
    cin >> n;
    a=(char*)malloc((n+1)*sizeof(char));
    i=0;
    while(i<=n){
        a[i]=0;
        i++;
    }

    i=2;
    while((j=i*i)<n){
        if(a[i]==0){
            cout << i << " ";
            while(j<=n){
                a[j]=1;
                j+=i;
            }
        }
        i++;
    }

    while(i<n){
        if(a[i]==0){
            cout << i << " ";
        }
        i++;
    }

    return 0;
}

Program di atas akan meminta input ketika dijalankan. Kalian bisa memasukkan nilai bilangan maksimal yang kalian inginkan dan menekan enter. Hasilnya akhirnya seharusnya akan sama dengan kode program sebelumnya jika inputnya 100.

Jika kalian ingin lebih cepat dan hemat array, berikut ini adalah versi yang sudah saya maksimalkan dan hanya menggunakan array dengan ukuran setengah dari jumlah data karena mengabaikan bilangan genap selain 2.

#include <stdio.h>
#include <stdlib.h>

int main(){
char *a;
int angka=0;
int kelipatan=0;
int x=0;
int y=0;
int n=100;
       //tentukan jumlah maksimal dan alokasikan memori

       //scanf("%d", &n);
       y=n/2;
       a=(char*)malloc(y*sizeof(char));
       //

       while(angka<y){
           a[angka]=0;
           angka++;
       }


       if(n>2){
           printf("%d", 2);
       }

       angka=3;

       while((kelipatan=angka*angka)<=n){
           y=(kelipatan-3)/2;
           x=angka+angka;
           if(a[y]==0){
                   printf(", %d", angka);
                   while(kelipatan<=n){
                       a[y]=1;
                       kelipatan+=x;
                       y+=angka;
                   }
           }
           angka+=2;
       }

       y=(angka-3)/2;

       while(angka<=n){
           if(a[y]==0){
               printf(", %d", angka);
           }
           angka+=2;
           y++;
       }

       printf(".");
       free(a);
       //system("pause");
}