by Dinesh Thakur Category: Control Structures

The Greatest Common Divisor of two positive integers can be calculated iteratively by the following formula known as Euclid's algorithm. You can see that this is a recursive definition with GCD(m,n) defined in terms of GCD(n,m%n).

GCD(m,n) = GCD (n,m) if n>m

=m, if n=0

= GCD(n, m%n) otherwise

We can also compute the Least Common Multiple of the two integers by using the following relation between the GCD and the LCM.

LCM * GCD = m * n

The C program given below uses Euclid's algorithm to compute the GCD and the LCM of two integers.

#include<stdio.h>

#include<stdlib.h>

int main()

{

long n, m, temp, big, small;

long gcd , lcm;

clrscr();

printf("\n Enter two integers ");

scanf("%ld %ld", &n , &m);

if(n==0||m==0)

{

printf("\n ERROR: one of the values equals O.");

exit(0);

}

big=n;

small=m;

while(small!=0)

{

if(big<small)

{

temp=big;

big=small;

small=temp;

}

printf("\n %ld %ld", big , small);

temp=big%small;

big=small;

small=temp;

}

gcd=big;

lcm=m*(n/big);

printf("\n\n GCD of %ld and %ld is %ld\n", n , m, gcd);

printf("\n LCM of %ld and %ld is %ld\n", n , m , lcm);

return 0;

}

About Dinesh Thakur

Dinesh Thakur holds an B.SC (Computer Science), MCSE, MCDBA, CCNA, CCNP, A+, SCJP certifications. Dinesh authors the hugely popular Computer Notes blog. Where he writes how-to guides around Computer fundamental , computer software, Computer programming, and web apps. For any type of query or something that you think is missing, please feel free to Contact us.

Search Content

Popular Article

#### Explain control statements those are used in C programming language

#### Write a C program for a menu driven program which has following options:

#### Write a program in C programming language to print weekdays using switch statement

#### Write a C program to display a table of squares and cubes.

#### What is the difference between 'for' and 'while' loops

#### C Program Print Odd Numbers in a given range m to n

#### Why to avoid goto in C

#### Define iteration Statements

#### Add numbers until a negative or zero is encountered

#### C Program Count Number of odd and even digits in a given integer number

#### C Program Prints Prime Numbers in a given range m to n

#### C Program Print a comma-separated list of numbers from 1 to 10

#### C Program Print Pythagorean triplets

#### C Program Sum of Digits of a Given Integer Number with do-while loop

#### C program to sum the series 1+1/2 + 1/3...+ 1/n

#### C Program for GCD using Euclid’s algorithm

#### C Program Date is Valid or Not

#### When is a switch statement better than multiple if statements

#### C program to calculate tax, given the following conditions

#### C Program Prime factors of a given number

#### C Program for print a name of color that start with a given character

#### is a default case necessary in a switch statement

#### What are the limitations with switch statement

#### C Program square and cube of first n natural numbers

#### C Program for string encryption using Caesar cipher (shift encoding).

#### C Program print a given integer number in words

#### C Program Sum of Digits of a Given Integer Number

#### C Program for Print integer number in a given range

#### What is the difference between IF-ELSE and SWITCH?

#### Nested if Statements in C Language

#### Find the efficiency of the worker.

#### C Program Sum of digits of number repeatedly to obtain a single-digit number

#### C Program Four digit special perfect square numbers

#### C program for Print a line of dashes

#### while loop in C

#### C Program Character test letter, vowel, consonant

#### C Program division without causing a division by zero error

#### C Program for Rational Approximations for Real Numbers

#### switch Statement in C

#### C Program Reverse digits in an integer number

#### C Program for GCD of Two Integers using Euclid's algorithm

#### C Program find the absolute value of a given Number

#### C Program for Print all uppercase letters followed by all lowercase letters on the next line

#### C Program Find the Result of a student in SSC Examination

#### C Program Find The Days in February

#### C Program Calculation of Perfect Numbers

#### do ... while Loop in C

#### C Programming for Loop

#### Block Statements in the if Statement

#### C Program for Simple Calculator

#### continue Statement in C Language

#### C Program Data entry Validation

#### C Program Accept data from the keyboard until correct data is entered

#### C Program Find The Larger between Two Numbers

#### Money payment: add numbers until desired sum is obtained

#### C Program Determine sum and average of several numbers entered from the keyboard.

#### C Program Find the Validity of marks in a single subject

#### C Program Examination result in a single subject with data validation

#### C Program for print a given digit as a word

#### C program Test for whitespace

#### C Program for Print integer number from 100 to 0 in steps of -10

#### Endless for loop in C

#### Compound Conditions in a While in C

#### C program to sum the series

#### Nested Loops in C

#### break Statement in C Language

#### Nested While Statements in C

#### C calculating Integration using Trapezoidal Rule

#### Compound Conditions In For loop in C

#### Nested FOR Loops in C

Basic Courses

Advance Courses