ProgrammingThis 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.
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 LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
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.
Distribution: SuSE Linux / Scientific Linux / [K|X]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!
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.
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.
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?
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.
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..
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.