Euclid Algoritması en büyük ortak böleni (EBOB)[GCD (Greatest Common Divisor )] bulmak için kullanılabilecek en etkin algoritmalardan biridir. O((logn)2) zaman karmaşıklığına sahiptir.
ebob(m, n) = ebob(n, m mod n) ‘i doğrulayacak şekilde çalışır.
Pseudocode ile :
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Euclid(m, n) | |
| //Euclid algoritmasını kullanarak ebob(m, n) değerini hesaplar | |
| //Input: m ve n isminde negatif olmayan, ikisi beraber sıfırdan farklı tam sayılar | |
| //Output: m ve n'nin ebob değeri | |
| while n != 0 do | |
| r ← m mod n | |
| m ← n | |
| n ← r | |
| return m |
Java kodu :
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Euclid { | |
| static int iterativeGCD(int m, int n){ | |
| while(n != 0){ | |
| int r = m % n; | |
| m = n; | |
| n = r; | |
| } | |
| return m; | |
| } | |
| static int recursiveGCD(int m, int n){ | |
| if(n == 0) | |
| return m; | |
| else{ | |
| return recursiveGCD(n, m % n); | |
| } | |
| } | |
| } |
