# GCD/LCM problems

RWilson

Greenhorn

Posts: 8

posted 8 years ago

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,

alex

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

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

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,

alex

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

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

megha joshi

Ranch Hand

Posts: 206

RWilson

Greenhorn

Posts: 8

posted 8 years ago

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 ]

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

posted 8 years ago

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

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

author

Sheriff

Sheriff

Posts: 8898

5

posted 8 years ago

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

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

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

Posts: 206

posted 8 years ago

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

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