Euclidean algorithm
algorithm for computing greatest common divisors
The Euclidean algorithm is an algorithm. It can be used to find the biggest number that divides two other numbers (the greatest common divisor of two numbers).
What the algorithm looks like in words
Euclid solved the problem graphically. He said
- If you have two distances, AB and CD, and you always take away the smaller from the bigger, you will end up with a distance that measures both of them.
The algorithm as an enumerated list
Start out with two positive integers m and n.
- If the value of m is less than the value of n, switch the values of m and n
- Find a number r equal to m modulo n
- Let m have the same value as n
- Let n have the same value as r
- If n does not have the value of 0, go to step 2
- The wanted value is in m.
The algorithm in pseudocode
Note: This pseudocode uses modular arithmetic instead of subtraction. It does the same thing as above, but gets the answer faster.
Precondition: two positive integers m and n
Postcondition: the greatest common integer divisor of m and n
if m < n, swap(m,n)while n does not equal 0 r = m mod n m = n n = rendwhileoutput m
C/C++ source code
Iterative (Non-recursive):
int euclid_gcd(int m, int n){int temp = 0;if(m < n){temp = m;m = n;n = temp;}while(n != 0){temp = m % n;m = n;n = temp;}return m;}
Recursive:
int euclid_gcd_recur(int m, int n){if(n == 0)return m;return euclid_gcd_recur(n, m % n);}
🔥 Top keywords: Main PageSpecial:SearchSupreme Court of the United StatesList of UEFA European Championship finalsWikipedia:AboutList of U.S. statesHelp:ContentsHelp:IntroductionKnights of the Round TableList of Disney moviesBlackSpecial:RecentChangesGodzilla X Kong: The New EmpireList of people who have walked on the MoonList of U.S. states and territories by time zoneUnited StatesThe Garfield MovieEducation24-hour clockEid al-AdhaGolden EdgeQueen (band)List of countries by continentsAviciiBig Mac IndexAdolf Hitler UunonaUmro Ayyar - A New BeginningMurder of Junko FurutaHelp:Authority controlCristiano RonaldoBismillahir Rahmanir Raheem19 Kids and CountingSOLID (object-oriented design)Jude BellinghamXXXTentacionLisa SparxxxPeriodic tableList of fruitsBTS