# Euclid’s Algorithm

Problem: how to find the greatest common divisor of two integers? Greatest common divisor is the largest integer number that divides both of those two numbers.

## Solution in C

Here is the solution to the problem written in C language:

```#include <stdlib.h> #include <stdio.h>   // Euclid's Algorithm // find greatest common divisor of two integers // which is the largest positive interger which // evenly divides both numbers   int main(void) {   int m = 128, n = 64, great_div; int reminder = 1, m1, n1;   m1 = m, n1 = n;   reminder = m % n;   while (reminder !=0) { m = n; n = reminder; reminder = m % n; }   great_div = n;   printf("Greatest common divisor of %d and %d is: %d\n", \ m1, n1, great_div);   return EXIT_SUCCESS; }```

## Solution in C++

The same problem solved in C++ but there’s not so much difference, the logic is exactly the same syntax, only difference is at printing the result and including C++ library”

```#include <iostream>   using namespace std;   int main(void) {   int m = 21, n = 3, great_div; int reminder = 1, m1, n1;   m1 = m; n1 = n;   reminder = m % n;   while (reminder != 0) { m = n; n = reminder; reminder = m % n; }   great_div = n; cout << "greatest common divisor of " << m1 << " and "\ << n1 << " is " << great_div << endl;   return EXIT_SUCCESS; }```

## Solution in Python

Finding the great common divisor of two numbers (Euclid’s Algorithm) written in Python is as follows. Of course is the same logic, just the syntax will differ.

```#!/usr/bin/python   m = 3 n = 27 great_div = reminder = None   m1 = m n1 = n   reminder = m % n   while reminder !=0: m = n n = reminder reminder = m % n   great_div = n print "Greatest common divisor of %d and %d is %d" %(m1, n1, n)```

## Solution in PHP

The solution to our problem about finding the great common divisor of two numbers (Euclidâ€™s Algorithm) written in PHP is presented next.

```<?php \$m = 27; \$n = 3; \$reminder = \$great_div = 0;   \$m1 = \$m; \$n1 = \$n;   \$reminder = \$m % \$n; while ( \$reminder !=0 ) { \$m = \$n; \$n = \$r; \$reminder = \$m % \$n; }   \$great_div = \$n;   echo "Greatest common divider of ", \$m1, " and ", \$n1, " is ", \$great_div; ?>```

## Solution in JavaScript

For JavaScript solution of finding greatest common divider we will have two file, a HTML file (euclid.html) which we will load in our browser and the javascript file (euclid.js) where all the magic is happening:

```<html> <head> <title>Greatest Common Divider Problem solved in JavaScript</title> <script type="text/javascript" src="euclid.js"></script> </head>   <body> <p id="displayGreatestDivider"></p> </body> </html>```

and our JavaScript file:

```window.onload = echoGreatestCommonDivider;   function echoGreatestCommonDivider() { var m = 128, n = 40; var reminder, great_div; var m1, n1;   m1 = m, n1 = n;   reminder = m % n;   while ( reminder != 0) { m = n; n = reminder; reminder = m % n; }   great_div = n;   document.getElementById("displayGreatestDivider").innerHTML = "Greatest\ common divider of " + m1 + " and " + n1 + " is " + great_div; }```