Mencari Bilangan Prima

Sebelumnya, mari kita cari tahu dulu apa arti dari bilangan prima itu,

Bilangan Prima adalah bilamgan yang hanya bisa dibagi 1 dan bilangan itu sendiri.

Ada beberapa implementasi bilangan prima yang ingin saya jelaskan disini, yaitu memeriksa apakah n = bilangan prima dan mencetak bilangan prima dari 1 sampai n.

~~~

1. memeriksa apakah n = bilangan prima

Implementasi kodenya kurang lebih seperti ini

#include <iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	bool isprime=true; //begin with true
	int i=2;
        //pengecualian untuk 2,bilangan genap yang prima
	if (n!=2) {
		while (isprime && i<n) {
			if (n%i==0) isprime=false;
			else i++;
			}
		}
	if (isprime) cout << "Prima\n";
	else cout << "Bukan Prima\n";
	}

Penjelasan : Maksud dari kode ini adalah, pertama kita set satu boolean isprime yang bernilai true. Lalu kita cek apakah n!=2. Kalau n!=2 maka bandingin sama nilai i. Kalau n%i=0 maka isprime jadi false, kalo belum increment nilai i sampai n-1.

2. mencetak bilangan prima dari 1 sampai n

Untuk implementasi ini, kita menggunakan suatu metode yang bernama Sieve of Eratosthenes, yaitu : “Bilangan prima apabila dikalikan dengan bilangan prima maka hasilnya bukan bilangan prima”

Implementasi :

#include <iostream>
#include <cstring> //to active memset()
using namespace std;
int main() {
	int n;
	cin >> n;
	bool prime[n];
	prime[0]=prime[1]=false;
	memset(prime,true,sizeof(prime));
        //fill all value of prime with true
	for (int i=2;i<=n;i++) {
		for (int j=2;i*j<=n;j++) {
                        //prime*prime=not prime
			prime[i*j]=false;
			}
		}
	for (int i=2;i<=n;i++) {
		if (prime[i]) cout << i << " ";
		}
	cout << endl;
	}

Referensi

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s