Win a copy of Java EE 8 High Performance this week in the Java/Jakarta EE forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# GCD/LCM problems

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

alex

[ October 28, 2007: Message edited by: a br ]
[ October 28, 2007: Message edited by: Jim Yingst ]

Ranch Hand
Posts: 206
Hi...

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

Thanks,
Megha

RWilson
Greenhorn
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

AND

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

AND

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 ]

RWilson
Greenhorn
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)}.

author
Sheriff
Posts: 8955
17
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!

Bert

megha joshi
Ranch Hand
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
}
n++;
}
System.out.println("The gcd is " + f);
}
}

//} // Extra Bracket

RWilson
Greenhorn
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?