Skip to main content

GCD ( Using Euclid's algorithm ) And LCM


The number 54 can be expressed as a product of two integers in several different ways:
 54 \times 1 = 27 \times 2 = 18 \times 3 = 9 \times 6. \,
Thus the divisors of 54 are:
 1, 2, 3, 6, 9, 18, 27, 54. \,
Similarly the divisors of 24 are:
 1, 2, 3, 4, 6, 8, 12, 24. \,
The numbers that these two lists share in common are the common divisors of 54 and 24:
 1, 2, 3, 6. \,
The greatest of these is 6. That is the greatest common divisor of 54 and 24. One writes:
 \gcd(54,24) = 6. \,

Using Euclid's algorithm

\gcd(a,0) = a
\gcd(a,b) = \gcd(b, a \,\mathrm{mod}\, b),
 a \,\mathrm{mod}\, b = a - b \left\lfloor {a \over b} \right\rfloor .
If the arguments are both greater than zero then the algorithm can be written in more elementary terms as follows:
\gcd(a,a) = a
\gcd(a,b) = \gcd(a - b,b)\quad, if a > b
\gcd(a,b) = \gcd(a, b-a)\quad, if b > a

Code to find the Greatest Common Divisor of two numbers.

int GCD(int a,int b)
    return a;

unsigned greatestCommonDivisor(unsigned m, unsigned n)
    if(n == 0) return m;
    return greatestCommonDivisor(n, m % n);
If we know the greatest common divisor (GCD) of integers a and b, we can calculate the LCM using the following formula.
LCM(a,b) =a × b


Popular posts from this blog

C Questions

C Questions
C Questions

Note : All the programs are tested under Turbo C/C++ compilers.
It is assumed that,
Programs run under DOS environment, The underlying machine is an x86 system, Program is compiled using Turbo C/C++ compiler.
The program output may depend on the information based on this assumptions (for example sizeof(int) == 2 may be assumed).
Predict the output or error(s) for the following:

void main()
int const * p=5; printf("%d",++(*p));
Compiler error: Cannot modify a constant value.
p is a pointer to a "constant integer". But we tried to change the value of the "constant integer".
char s[ ]="man"; int i;
for(i=0;s[ i ];i++)
printf("\n%c%c%c%c",s[ i ],*(s+i),*(i+s),i[s]);
Answer: mmmm
aaaa nnnn

Zoho Interview | Set 1 (Advanced Programming Round)

Third Round: (Advanced Programming Round) Here they asked us to create a “Railway reservation system” and gave us 4 modules. The modules were:
    1. Booking
    2. Availability checking
    3. Cancellation
    4. Prepare chart
We were asked to create the modules for representing each data first and to continue with the implementation phase.

 My Solution :

#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<string.h>#include<iostream.h>#include<time.h>#include<iomanip.h>#include<fstream.h>char f[10]="f";char s[10]="s";int addr,ad,flag,f1,d,m,i,amt;float tamt; class login {public:char id[100];char pass[100];char*password;void getid(){ cout<<"Enter your id:";gets(id); password=getpass("Enter the password:");strcpy(pass,password);}void displayid(){ cout<<"Id:";puts(id); cout<<"Password:";puts(pass);}}; class detail {public:in…

ORACLE 9i practice solutions

Created by BCL easyConverter SDK 3 (HTML Version)