Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game. 
Notices 
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
Are you new to LinuxQuestions.org? Visit the following links:
Site Howto 
Site FAQ 
Sitemap 
Register Now
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQrelated cookies.

Introduction to Linux  A Hands on Guide
This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.
Click Here to receive this Complete Guide absolutely free. 



10082008, 10:32 AM

#1

LQ Newbie
Registered: Aug 2008
Posts: 12
Rep:

Greatest common Divisor (GCD)
Shell program to find the Greatest common divisor (GCD) of the given three numbers.
Please help me.
Thanks in advance.



10082008, 11:21 AM

#2

Senior Member
Registered: Dec 2005
Location: London, ON, Canada
Distribution: Arch, Ubuntu, Slackware, OpenBSD, FreeBSD
Posts: 1,853
Rep:

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 copyandpaste 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.



10082008, 08:22 PM

#3

Guru
Registered: Aug 2004
Location: Sydney
Distribution: Centos 6.6, Centos 5.10
Posts: 16,352




10082008, 11:40 PM

#4

Senior Member
Registered: Mar 2007
Location: Russia
Distribution: Slackware 12.2
Posts: 1,202
Rep:

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.



10092008, 08:28 AM

#5

Senior Member
Registered: Dec 2005
Location: London, ON, Canada
Distribution: Arch, Ubuntu, Slackware, OpenBSD, FreeBSD
Posts: 1,853
Rep:

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 easilytranslatable syntax.



10092008, 10:50 AM

#6

Member
Registered: Aug 2005
Distribution: SuSE Linux / Scientific Linux / [KX]ubuntu
Posts: 273
Rep:

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!



10132008, 10:32 AM

#7

LQ Newbie
Registered: Aug 2008
Posts: 12
Original Poster
Rep:

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.



10132008, 11:06 AM

#8

Senior Member
Registered: Mar 2007
Location: Russia
Distribution: Slackware 12.2
Posts: 1,202
Rep:

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 nonprime 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.
Last edited by ErV; 10132008 at 11:23 AM.



10132008, 12:36 PM

#9

Senior Member
Registered: Sep 2003
Posts: 3,171
Rep:

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



10132008, 10:10 PM

#10

LQ Newbie
Registered: Aug 2008
Posts: 12
Original Poster
Rep:

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.



10132008, 10:25 PM

#11

ReliaFree Maintainer
Registered: Aug 2004
Location: Kalamazoo, Michigan
Distribution: Slackwarecurrent, Cross Linux from Scratch, Gentoo
Posts: 2,765

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?



10132008, 11:12 PM

#12

Guru
Registered: Aug 2004
Location: Sydney
Distribution: Centos 6.6, Centos 5.10
Posts: 16,352

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



10142008, 05:23 AM

#13

LQ Newbie
Registered: Aug 2008
Posts: 12
Original Poster
Rep:

Bad forum for a beginer



10142008, 05:41 AM

#14

Senior Member
Registered: Mar 2007
Location: Russia
Distribution: Slackware 12.2
Posts: 1,202
Rep:

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.



10142008, 07:38 AM

#15

Guru
Registered: Aug 2003
Distribution: CentOS, OS X
Posts: 5,131
Rep:

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..



Thread Tools 
Search this Thread 


Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



All times are GMT 5. The time now is 03:32 PM.

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.

Latest Threads
LQ News

