LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   linux programe for finding GCD of two numbers (https://www.linuxquestions.org/questions/programming-9/linux-programe-for-finding-gcd-of-two-numbers-752041/)

 yoga 09-02-2009 05:21 AM

linux programe for finding GCD of two numbers

i am M.Sc. electronics student.please help me in constructing linux program for G.C.D. of two numbers.And also i want logic of this program

 hyperactive22 09-02-2009 07:20 AM

A trivial solution to find LCM is as follows:

do
{
if (a < b)
{
temp = a ;
a = b;
b = temp;
}
a = a - b ;
}while(b) ;

Here a and b are the input values to program
and the final value of a is the LCM

Then use this equation:
GCD * LCM = a * b
to find GCD.

 idgl 09-30-2009 03:55 AM

Euclid's algorithm to find the greatest common divisor of two
positive integers, m and n. See D. Knuth 'The Art of Computer
Programming'
, Volume 1, page 2.
(1) Divide m by n and let r be the remainder.
(2) If r equals 0 the algorithm terminate; n is the answer.
(3) Set m to n, n to r and go back to step (1).

#!/bin/bash
m=\$1
n=\$2
while true
do
r=\$(( \$m % \$n )) # (1) Divide m by n and let r be the remainder.
if [ \$r -eq 0 ] # (2) If r equals 0 the algorithm terminate; n is the answer.
then
echo \$n
break
fi
m=\$n # (3) Set m to n, n to r and go back to step (1).
n=\$r
done

 All times are GMT -5. The time now is 09:55 AM.