kidzsearch.com > wiki Explore:web images videos games

# Euclidean algorithm

KidzSearch Safe Wikipedia for Kids.

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).

## Contents

## 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 = r endwhile output 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; else return euclid_gcd_recur(n, m % n); }