wood burning stoves 2.0
The moose likes Beginning Java and the fly likes GCD/LCM problems Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "GCD/LCM problems" Watch "GCD/LCM problems" New topic

GCD/LCM problems


Joined: Sep 25, 2007
Posts: 8
I've been having problems with creating a GCD program. Does anyone know what's wrong with it!!!? Here it is below:

I'm also having problems making a LCM (least common multiple) program. I want it to be similar to the one above, but I can't figure out where to start.

Thanks anyone for your help,


[ October 28, 2007: Message edited by: a br ]
[ October 28, 2007: Message edited by: Jim Yingst ]
megha joshi
Ranch Hand

Joined: Feb 20, 2007
Posts: 206

Can you write a step wise algorithm that you are using to find the gcd ...
Also solve it for a example...
Say a = 22...b = 44.

Write down the algorithm and then I will help you with the rest...


Joined: Sep 25, 2007
Posts: 8
Sure! Here are the directions I received:

Your task is to write the following program in the GCD.java file. The program first reads in 2 integer numbers a and b. Then the program computes and prints the Greastest Common Divider (GCD) of the numbers a and b.

The GCD of a and b is the largest integer n, such that:

a / n has a remainder 0


b / n has a remainder 0

# More details...

The GCD cannot be computed with some Mathematical formula, but you need to search and find it.

The number of integers is infinite, so you need to limit the range to search.

Use these facts to limit the range:

o The GCD of a and b must be smaller than either one of a or b.

* You program try every number (starting from 1 until the largest one possible) in the possible range and test if it is a common divider.

A common divider is a number n, such that:

a / n has a remainder 0


b / n has a remainder 0

* Don't forget that you can perform AND, OR and NOT operation of logic values:

o the AND operator is: &&
o the OR operator is: ||
o the NOT operator is: !

* Finding the greatest common divider can be achieved by always keeping the larger common divider if you find a new one.

# Hint

* Try every number starting from 1 upto one of the input numbers (any one of the input numbers will do)

* The program must remember (save it in a variable - memory !) the last number that divides both input numbers

* After you try every number, print out the last number that you have recorded.
[ October 28, 2007: Message edited by: a br ]

Joined: Sep 25, 2007
Posts: 8
As for the algorithm: I found this on wikipedia:
Calculating the GCD

Greatest common divisors can in principle be computed by determining the prime factorizations of the two numbers and comparing factors, as in the following example: to compute gcd(18,84), we find the prime factorizations 18 = 2�32 and 84 = 22�3�7 and notice that the "overlap" of the two expressions is 2�3; so gcd(18,84) = 6. In practice, this method is only feasible for very small numbers; computing prime factorizations in general takes far too long.

A much more efficient method is the Euclidean algorithm, which uses the division algorithm in combination with the observation that the gcd of two numbers also divides their difference: divide 84 by 18 to get a quotient of 4 and a remainder of 12. Then divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a remainder of 0, which means that 6 is the gcd.

The series of quotients generated by the Euclidean algorithm compose a continued fraction.

If a and b are not both zero, the greatest common divisor of a and b can be computed by using least common multiple (lcm) of a and b:

\operatorname{gcd}(a,b)=\frac{a\cdot b}{\operatorname{lcm}(a,b)}.
Bert Bates

Joined: Oct 14, 2002
Posts: 8898
Howdy "a br" -

We've found that things stay a lot friendlier here at the ranch when folks use their real names as their display names. Please update your display to match our policy.

Thanks, and welcome to the ranch!


Spot false dilemmas now, ask me how!
(If you're not on the edge, you're taking up too much room.)
megha joshi
Ranch Hand

Joined: Feb 20, 2007
Posts: 206
import java.util.Scanner;
public class GCD{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a;
int b;
int n;
System.out.println("GCD FINDER");
System.out.println("Enter integer \"a\": ");
a = in.nextInt();
System.out.println("Enter integer \"b\": ");
b = in.nextInt();
n = 1;
int f=1; //Local variables must always be initialized, else compiler error
while (n <= a) {
if (a % n == 0 && b % n == 0) {
// int f // You are redeclaring f inside loop why???
f = n;
//n++; // You want to increment to check next number regardless of whether it is dividing both numbers a and b
// So this n++ should be outside if condition
System.out.println("The gcd is " + f);

//} // Extra Bracket

Joined: Sep 25, 2007
Posts: 8
Thank you so much, its starting to make sense now. Could you point me in the right direction for creating a LCM program?
I agree. Here's the link: http://aspose.com/file-tools
subject: GCD/LCM problems
It's not a secret anymore!