Skip to content

April 23, 2013

Euclid’s Algorithm

by noise

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;
 }
Read more from Programming Noise

Leave a Reply

required
required

Note: HTML is allowed. Your email address will never be published.

Subscribe to comments