LinuxQuestions.org
Support LQ: Use code LQ3 and save $3 on Domain Registration
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
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



Reply
 
Search this Thread
Old 10-08-2008, 10:32 AM   #1
man5237
LQ Newbie
 
Registered: Aug 2008
Posts: 12

Rep: Reputation: 0
Greatest common Divisor (GCD)


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


Please help me.

Thanks in advance.
 
Old 10-08-2008, 11:21 AM   #2
indienick
Senior Member
 
Registered: Dec 2005
Location: London, ON, Canada
Distribution: Arch, Ubuntu, Slackware, OpenBSD, FreeBSD
Posts: 1,853

Rep: Reputation: 65
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.
 
Old 10-08-2008, 08:22 PM   #3
chrism01
Guru
 
Registered: Aug 2004
Location: Sydney
Distribution: Centos 6.6, Centos 5.10
Posts: 16,324

Rep: Reputation: 2041Reputation: 2041Reputation: 2041Reputation: 2041Reputation: 2041Reputation: 2041Reputation: 2041Reputation: 2041Reputation: 2041Reputation: 2041Reputation: 2041
I'd say homework: see http://www.linuxquestions.org/questi...number-675050/
 
Old 10-08-2008, 11:40 PM   #4
ErV
Senior Member
 
Registered: Mar 2007
Location: Russia
Distribution: Slackware 12.2
Posts: 1,202
Blog Entries: 3

Rep: Reputation: 62
Quote:
Originally Posted by man5237 View Post
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.
 
Old 10-09-2008, 08:28 AM   #5
indienick
Senior Member
 
Registered: Dec 2005
Location: London, ON, Canada
Distribution: Arch, Ubuntu, Slackware, OpenBSD, FreeBSD
Posts: 1,853

Rep: Reputation: 65
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.
 
Old 10-09-2008, 10:50 AM   #6
unihiekka
Member
 
Registered: Aug 2005
Distribution: SuSE Linux / Scientific Linux / [K|X]ubuntu
Posts: 273

Rep: Reputation: 32
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!
 
Old 10-13-2008, 10:32 AM   #7
man5237
LQ Newbie
 
Registered: Aug 2008
Posts: 12

Original Poster
Rep: Reputation: 0
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.
 
Old 10-13-2008, 11:06 AM   #8
ErV
Senior Member
 
Registered: Mar 2007
Location: Russia
Distribution: Slackware 12.2
Posts: 1,202
Blog Entries: 3

Rep: Reputation: 62
Quote:
Originally Posted by man5237 View Post
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.

Last edited by ErV; 10-13-2008 at 11:23 AM.
 
Old 10-13-2008, 12:36 PM   #9
jiml8
Senior Member
 
Registered: Sep 2003
Posts: 3,171

Rep: Reputation: 115Reputation: 115
Wow. I didn't know that posts on this site could get deleted. I put a post on this thread...and it is gone!
 
Old 10-13-2008, 10:10 PM   #10
man5237
LQ Newbie
 
Registered: Aug 2008
Posts: 12

Original Poster
Rep: Reputation: 0
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.
 
Old 10-13-2008, 10:25 PM   #11
weibullguy
ReliaFree Maintainer
 
Registered: Aug 2004
Location: Kalamazoo, Michigan
Distribution: Slackware-current, Cross Linux from Scratch, Gentoo
Posts: 2,755
Blog Entries: 1

Rep: Reputation: 238Reputation: 238Reputation: 238
Quote:
Originally Posted by man5237 View Post
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 View Post
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?
 
Old 10-13-2008, 11:12 PM   #12
chrism01
Guru
 
Registered: Aug 2004
Location: Sydney
Distribution: Centos 6.6, Centos 5.10
Posts: 16,324

Rep: Reputation: 2041Reputation: 2041Reputation: 2041Reputation: 2041Reputation: 2041Reputation: 2041Reputation: 2041Reputation: 2041Reputation: 2041Reputation: 2041Reputation: 2041
LQ rules forbid doing someone's homework for them. Not going to happen...
 
Old 10-14-2008, 05:23 AM   #13
man5237
LQ Newbie
 
Registered: Aug 2008
Posts: 12

Original Poster
Rep: Reputation: 0
Bad forum for a beginer
 
Old 10-14-2008, 05:41 AM   #14
ErV
Senior Member
 
Registered: Mar 2007
Location: Russia
Distribution: Slackware 12.2
Posts: 1,202
Blog Entries: 3

Rep: Reputation: 62
Quote:
Originally Posted by man5237 View Post
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.
 
Old 10-14-2008, 07:38 AM   #15
b0uncer
Guru
 
Registered: Aug 2003
Distribution: CentOS, OS X
Posts: 5,131

Rep: Reputation: Disabled
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..
 
  


Reply

Tags
script, shell


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
What is the greatest software ever ? marozsas Linux - News 1 08-20-2006 09:37 AM
BOGUS.common.04y -> /home/common/Mailbox jayakrishnan Linux - Networking 0 11-19-2005 05:48 AM
the greatest site thanko LQ Suggestions & Feedback 3 12-28-2004 10:16 AM
GCD Algo. Help dontcare Programming 2 10-16-2004 10:50 PM
Isn't Linux the greatest! perry General 8 06-12-2004 04:26 AM


All times are GMT -5. The time now is 08:50 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration