Algoritma bilangan prima, pangkat, dan FPB

1. Algoritma mencari pangkat : Sieve of eratosthenes algorithm
2. Algoritma pemangkatan metode divide and conquer
3. Algoritma mencari GCD :euclid
1. Sieve of Eratosthenes
bilangan prima adalah bilangan yang hanya habis di bagi 1 dan dirinya sendiri, contohnya 2,3,5,7,11,dst
secara naif kita bisa tahu suatu bilangan X itu prima atau bukan dengan mengecek sisa baginya dari 2 sampai dengan akar X.
jika ada suatu angka dari 2 sampai akar X itu yg habis membagi X, maka X dipastikan bukan prima. namun teknik ini cukup lambat .
jika kita diharuskan untuk menggenerate bilangan prima dari 1 sampai X. untuk itu diperlukan algoritma yang lebih cepat untuk menghandle masalah ini.
Cara kerja sieve of eratosthenes ini cukup simple.
1. kita siapkan array seukuran X, prime[i] bernilai true jika i adalah bilangan prima, begitu pula sebaliknya
2. pertama kita set prime[1] sebagai false (angka 1 bukan prima), lalu kita set sisanya true
3. kita loop i dari 1 sampai akar X, jika prime[i] itu true (bilangan prima), berarti kita set semua kelipatan i itu sebagai false
4. jika proses diatas sudah selesai, kita sudah punya array berisi informasi suatu bilangan itu prima atau bukan
code in C++, generate bilangan prima dari 1 sampai 1 000 000
for (int i=2;i<=1000000;i++) prime[i]=1;
for (int i=2;i*i<=1000000;i++){
if (prime[i]){
for (int j=i*i;j<=1000000;j+=i) prime[j]=0;
}
}
2. Pemangkatan metode divide and conquer
diberikan A dan B, bilangan integer, berapa hasil dari A pangkat B modulus 10000?? (kenapa di modulus 10000? biar angkanya gak kegedean)
cara naifnya adalah mengalikan A sebanyak B, yang kompleksitasnya O(B). dengan metode divide and conquer, kompleksitasnya ialah
O( log B). jauh lebih cepat. sebagai perbandingan, cara divide & conquer bisa menghitung 2 pangkat 1 triliyun kurang dari 100
proses.
ide algoritma ini kira2 seperti ini:
A pangkat B = A jika B = 1
A pangkat B = A*A pangkat B/2 jika B genap
A pangkat B = A * (A pangkat B-1) jika B ganjil
untuk lebih jelasnya kita hitung 2 pangkat 10
2 pangkat 10
= 4 pangkat 5
= 4* (4 pangkat 4)
= 4* (16 pangkat 2)
= 4* (256 pangkat 1)
= 4* 256
= 1024
(selesai kurang dari 10 proses)
code in C++, untuk menghitung a pangkat b
int pangkat(int a,int b){
int res=1;
while (b){
if (b%2){
b--;
res=(res*a)%10000;
}
else {
b/=2;
a=(a*a)%10000;
}
}
return res;
}
3. mencari GCD
GCD (greatest common divisor) atau FPB (faktor persekutuan terbesar) dari dua bilangan A dan B adalah suatu angka terbesar yang
membagi habis A dan B. sebagai contoh FPB dari 15 dan 24 adalah 3, FPB 7 dan 121 adalah 1
Untuk mencari GCD dari A dan B adalah:
1. jika A lebih kecil dari B, tukar A dan B
2. jika A modulus B = 0, gcd adalah B, jika tidak ke step 3
3. A = B, dan B= A modulus B, kembali ke step 2
code in C++
view sourceprint?
int GCD(int a,int b){
if (a < b) swap(a,b);
while (a%b){
int tmp=a%b;
a=b;
b=tmp;
}
return b;
}

Posted in: kampus