LinuxQuestions.org

LinuxQuestions.org (/questions/)
-   Programming (http://www.linuxquestions.org/questions/programming-9/)
-   -   linux programe for finding GCD of two numbers (http://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 07:34 AM.