Greatest common Divisor (GCD)

man5237 · 10-08-2008, 10:32 AM

Shell program to find the Greatest common divisor (GCD) of the given three numbers.

Please help me.

Thanks in advance.

indienick · 10-08-2008, 11:21 AM

Homework, perhaps?

Here's a test in Common Lisp (I do not know Bash scripting well enough to be able to do mathematics in it):

Code:

#!/usr/bin/env clisp
(when (not (null *args*))
  (let ((gcd 1) (numlist (list (first *args*) (second *args*) (third *args*))))
    (dotimes (i (first *args*))
      (when (and (= (mod (first numlist) i) 0)
                 (= (mod (second numlist) i) 0)
                 (= (mod (third numlist) i) 0))
        (setf gcd i)))
    (format t "~&Greatest common divisor (factor) of ~d, ~d and ~d is ~d~%"
            (first numlist) (second numlist) (third numlist) gcd)))

Make sure you have the GNU/Clisp implementation installed, and copy-and-paste that text into a file.

EDIT: A note to anyone else who looks at this code; I know it's not the most efficient, and could be done with much less typing, but oh well.

chrism01 · 10-08-2008, 08:22 PM

I'd say homework: see http://www.linuxquestions.org/questi...number-675050/

ErV · 10-08-2008, 11:40 PM

Quote:

Originally Posted by man5237

Please help me.

No.

First post what have you tried, what doesn't work, where is the problem, and explain what you don't understand. Then people will help. Doing your homework instead of you isn't interesting.

indienick · 10-09-2008, 08:28 AM

I saw the "Avogadro" post as well, and after some thought, definitely homework.

*snicker* Oh well, it's not like I gave him an answer in a language with easily-translatable syntax.

unihiekka · 10-09-2008, 10:50 AM

Ever heard of google or search engines in general? On the first page of hits, there are lots of GCD sample scripts...

Furthermore, thinking about it yourself, doesn't hurt - homework is there for you to learn something, not just to keep you from doing stuff you'd rather do!

man5237 · 10-13-2008, 10:32 AM

I got a solution to find the GCD of two numbers , but I don't know how to write a program to find the GCD of three numbers.

Program to find GCD of two number is the following.

Quote:

echo "Enter first number"
read n1
echo "Enter the second number"
read n2
gcd=0
if test $n1 -gt $n2
then
i=1
while test $i -le $n1
do
a=`expr $n1 % $i`
b=`expr $n2 % $i`
if test $a -eq 0 -a $b -eq 0
then
if test $gcd -lt $i
then
gcd=$i
fi
fi
i=`expr $i + 1`
done
fi
if test $n2 -gt $n1
then
i=1
while test $i -le $n2
do
a=`expr $n1 % $i`
b=`expr $n2 % $i`
if test $a -eq 0 -a $b -eq 0
then
if test $gcd -lt $i
then
gcd=$i
fi
fi
i=`expr $i + 1`
done
fi
echo GCD of $n1 and $n2 = $gcd

SO please write a program to find the GCD of 3 numbers.

Thanks.

ErV · 10-13-2008, 11:06 AM

Quote:

Originally Posted by man5237

I got a solution to find the GCD of two numbers , but I don't know how to write a program to find the GCD of three numbers.

The same way as for 2 numbers.

Any non-prime number can be represented as a multiply of several prime numbers.
Example:
142=2*71
246=2*3*41
586=2*293
Greatest Common Divisor is the multiply of all prime numbers that present in all given numbers at once. I.e. if some prime number is part of one argument but not another, it isn't part of GCD. For 142, 246 and 586 GCD is 2.

Example:
GCD of 2*2*2*3*3*7*11 (5544), 2*2*3*3*13(468) and 2*3*3*3*17(918) is 2*3*3(18). This is because from all arguments 3* is used at least two times and 2* is used at least once. All other numbers aren't shared among arguments.

Given this information it quite easy to make program that calculates GCD for any number of given arguments.

Still need algorithm? Here you go:
1) store GCD variable with initial value of one
2) Store divisor variable with initial value of two
3) While all arguments are larger than (GCD*divisor)^2 do
3.1) Attempt to divide all arguments by (GCD*divisor)
3.2) If all arguments can be divided by (GCD*divisor) without remainder, multiply GCD by divisor value. If arguments can't be divided without remainder, increase divisor by one.
3.3) Go to 3.1
4( return value of GCD

Quote:

SO please write a program

If you won't write program yourself, you won't learn anything. People might help you with algorithm, explain some shell script quircks, but I don't think many will write program instead of you.

jiml8 · 10-13-2008, 12:36 PM

Wow. I didn't know that posts on this site could get deleted. I put a post on this thread...and it is gone!

man5237 · 10-13-2008, 10:10 PM

Please write a program to find the GCD of 3 numbers.

Please write the full program for me.

Please.

As 15th is the deadline to submit the program.

So please.

I tried but I cant.

Thank You.

weibullguy · 10-13-2008, 10:25 PM

Quote:

Originally Posted by man5237

Please write the full program for me.

Have you asked your instructor to write it for you? If he/she won't why would we?

Quote:

Originally Posted by man5237

I tried but I cant.

What have you tried to port your two number solution to three numbers? What was the result of everything you've tried (and I don't mean, "It didn't work.")? What do you think is wrong with what you've tried already? What have you researched that looked promising but wasn't?

chrism01 · 10-13-2008, 11:12 PM

LQ rules forbid doing someone's homework for them. Not going to happen...

man5237 · 10-14-2008, 05:23 AM

Bad forum for a beginer

ErV · 10-14-2008, 05:41 AM

Quote:

Originally Posted by man5237

Bad forum for a beginer

I gave you whole algorithm, in details. More than enough.

If you can't write implementation yourself, find freelancer resource and hire someone to write implementation instead of you. Task like this won't cost much.

b0uncer · 10-14-2008, 07:38 AM

When I need(ed) to find the greatest common divisor, I use(d) the Euclid's algorithm (see Wikipedia page). It's fairly simple and straightforward; if you do not understand what greatest common divisor means (or what prime numbers are), you can't probably understand how to calculate it either..and if you don't understand how to do it with paper and pencil, it's probably impossible to write a computer program (like a shell script) to do it. So get back to basics.

You could start by thinking the problem like this: if you have three numbers a, b and c and know how to calculate the greatest common divisor of any two of them, then how are the calculated GCDs related to each other? A few (simple) example calculations on paper (remember to divide numbers to multiplications of primes so you "get to the bottom of it") should reveal you something..