I'm teaching myself Java w/Dr. Liang's Intro to Java, 9th Ed., Comprehensive.....Chapter 4, Loops....in attempting to find the greatest common divisor (gcd) of two integers, n1 and n2, whereas k is a possible gcd and gcd is initialized to 1, the following code has been entered:

for (int k = 2; k <= n1 && k <= n2; k++) {

if ( n1 % 2 == 0 && n2 % 2 == 0)

gcd= k;

}

When asked to change the previous line of code to this:

for (int k = 2; k <= n1 / 2 && k < n2 / 2; k++){

the questions states this revision is wrong and to find the reason.....well, I've changed it, entered "3" (per the answer key) for n1 and n2....

now I can see logically where k (2 in this example) is not <= n1/2, which is 3/2 or 1, since we're dealing w/integers, yet when I compile and run, my answer is indeed, gcd = 1. However, since this is a Boolean expression where && is being used, since the first portion evaluates to "false", the 2nd portion isn't executed and thus my result of 1?......sorry, loops are throwing me for one, for sure....can someone clarify, please?

Thanks!

Knute Snortum wrote:I As you've described it, I don't see how k could be 1.

We also don't know what the values of n1 and n2 are. [Edit: Duh. Of course we don't. Forget I wrote that. ]

Are you familiar with Euclid's algorithm? Because the way they've shown you seems very primitive.

But it could be that they're trying to show you some good stuff about

`for`loops first, so don't worry too much about it.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

here's the exercise...

import java.util.Scanner;

public class Listing4_9GreatestCommonDivisor {

//** Main method */

public static void main(String[] args) {

//Create a Scanner

Scanner input = new Scanner(System.in);

//Prompt the user to enter two integers

System.out.print("Enter first integer: ");

int n1 = input.nextInt();

System.out.print("Enter second integer: ");

int n2 = input.nextInt();

int gcd = 1; //initial gcd is 1

for (int k = 2; k <= n1/2 && k <= n2/2; k++) {

if (n1 % k == 0 && n2 % k == 0)

gcd = k; //update gcd

}

System.out.println("The greatest common divisor for " + n1 +

" and " + n2+ " is " + gcd);

}

}

So I ran the program in NetBeans, entered 3 for both integers and my gcd was 1, yet was told the current 'for' loop was wrong by illustration....if one takes out the "/2" in the for loop, then it's correct.....yet I come up with the same answer w/o '/2' and if I used a 'while' loop as follows;

while (k <= n1 && k <= n2) {

if (n1 % 2 == 0 && n2 % 2 == 0)

gcd = k;

k++;

Hope this helps and illustrates things a bit better for everyone...

Eddie Gerlach wrote:now I can see logically where k (2 in this example) is not <= n1/2, which is 3/2 or 1, since we're dealing w/integers, yet when I compile and run, my answer is indeed, gcd = 1.

Right. So the question is: can you think of ANY two values for n1 and n2, where 2 is less than or equal to n1/2 and

*less than*n2/2, and the answer should NOT be 1? I can think of 1 (actually, 2 now that I've read the post correctly ).

Hint: I think they've deliberately made the question difficult by putting k on the

*left-hand*side of the expression because, for most people, it's not the way we think (well, not me). So, to help you out (maybe):

`k <= n1/2`can be rewritten as

`n1/2 >= k`

`k < n2/2`can be rewritten as

`n2/2 > k`

you should also remember that these are conditions for

*continuing*the loop, so if either of them is false when k=2, the loop will

*never*get executed.

HIH

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

thanks for the follow-up, but if I enter 3 and 6 (which means the answer should be 3 as the gcd), I still get 1.....however, when I enter 125 and 2525, I get 25....so it works part of the time....hmmmm, when I remove the divisor '/2' from both sides of the Boolean expression, I come up with 3.....I've done something foul and need to re-examine my code...God, I love and hate this all at the same time..

Eddie Gerlach wrote:Gosh, I'm a boob....the gcd of 3 and 3 is 3, not 1! Went back and examined my code.....when I enter the '/2' divisor in the 'for' loop and re-evaluate, it's an incorrect process to determine the "%" remainder, yes? swimming, swimming, swimming.....

Well done! That's what programming is about.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

The gcd will be 16, which we know isn't correct, it's 8. However, when k reaches 16:

k <= n1 && k <= n2 is true because k = 16 and 16 <= 24 and 16 <= 16

and

n1 % 2 == 0 && n2 % 2 == 0 is also true because 24 % 2 is 0 and 16 % 2 is 0.

So gcd becomes 16. On the next iteration k becomes 17 and the loop stops because k > n2.

Using

The gcd will be 7, which we know isn't correct, it's still 8. However, when k reaches 7:

k <= n1 / 2 && k < n2 / 2 is true because 7 <= 24 / 2 <= 12 and 7 < 16 / 2 <= 8

and

n1 % 2 == 0 && n2 % 2 == 0 is also true because 24 % 2 is 0 and 16 % 2 is 0.

So gcd becomes 7. On the next iteration k becomes 8 and the loop stops because k = n2.

Take what you know from the problem:

The user is entering two numbers, so you don't know which is larger.

At a minimum, a gcd will start with 1, so 1 can be used to start the for loop.

If the index for the for loop is greater than the smaller number then it cannot be a gcd.

What does this mean to do:

Determine the smaller of the two numbers.

Start your for loop at 1.

Stop the for loop when its index equals the smaller number.

Make sense?

thanks for the comprehensive explanation. Before Eddie replies, can you explain me

the following, for that's where I get lost:

1) you write "So gcd becomes 7. On the next iteration k becomes 8 and the loop stops because k = n2. "

Now, isn't n2 equal to 16 in your example? See above the first code.

2) in your second code, line 02, I see:

Can you explain why both n1 and n2 must be even for gcd to be increased? For example, if n1 = 22

and n2 = 11, do I get: gcd = 11?

Greetz,

Piet

Piet Souris wrote:2) in your second code, line 02, I see:...

@Emil: Piet got in before me, but that code is wrong. Eddie's code says

`if ( n1 %`...

**k**== 0 && n2 %**k**== 0) {and k is incremented every time, so you can't assume a constant.

Nevertheless, you get a cow for effort!

Winston

Articles by Winston can be found here

From what I can gather, 'while' these two conditions exist, AND if (n1 % k == 0

__&&__n2 % k == 0), then 'k' is incremented by 1...since it started at 2, shouldn't it then be incremented by 1 and then gcd is 3? However, since this is a Boolean statement that requires the first statement to evaluate as true, and if it doesn't, it ignores the 2nd condition? Then the loop starts anew until a new value is stored for gcd (or 'k') or k becomes >= n1 or n2?

Sorry, but noobie brainfarts and perhaps a bit "loop"y...

Eddie

Given:

n1 = 24

n2 = 16

In the second example, using the OPs code:

As the loop iterates and k becomes 7, the condition in the for loop, k <= n1 / 2 && k < n2 / 2, essentially becomes:

k = 7

n1 = 24

n2 = 16

k <= n1 / 2 && k < n2 / 2

7 <= 24 / 2 && 7 < 16 / 2

7 <= 12 && 7 < 8

The condition is true, so go into the loop body, where we see

which is

24 % 2 = 12 remainder 0 and 16 % 2 = 8 remainder 0

This condition is true so k (which is 7) is being assigned to gcd. On the next iteration, k is 8 and the second part of the loop condition (k < n2 / 2) is false because 8 is not less than 8. So gcd remains at 7.

In my example, n2 is always 16, but the second part of the loop condition is k < n2 / 2 which is the same as k < 16 / 2 which is the same as k < 8. I should have wrote:

"So gcd becomes 7. On the next iteration k becomes 8 and the loop stops because

**k = n2 / 2**."

For your second question, n1 and n2 don't have to be even, however when one is not even such as your example of 22 and 11, the gcd will always be its initialized value because one of the n1 % 2 == 0 && n2 % 2 == 0 conditions will be false. I was refering to the OPs code to illustrate where the issues with the conditions are (hence, gcd's of 16 and 7 when they should be 8).

Emil Jennings wrote:@Winston I was addressing issues in the original post.

Quite right. I was looking at the second post, where it had been corrected.

Winston

Articles by Winston can be found here

Eddie Gerlach wrote:Winston,

Thanks for catching that...I was simply reading from my textbook and I could've entered the code incorrectly....

Well, if your second post is from your textbook then it looks like you got it right. It

*should*be:

`n1 %`...

**k**== 0 &&Winston

Articles by Winston can be found here

'while' these two conditions exist, AND if (n1 % k == 0 && n2 % k == 0), then 'k' is incremented by 1...since it started at 2, shouldn't it then be incremented by 1 and then gcd is 3?

Yes

since this is a Boolean statement that requires the first statement to evaluate as true, and if it doesn't, it ignores the 2nd condition?

Yes

Then the loop starts anew until a new value is stored for gcd (or 'k') or k becomes >= n1 or n2?

Yes

Sorry, but noobie brainfarts and perhaps a bit "loop"y...

No need to be sorry, we're all here to learn...as long as you understand it then everything is good to go.

the original code used a while loop:

int gcd = 1; // initial gcd is 1

int k = 2; //possible gcd

while (k <= n1 %% k <= n2) {

if ( n1 % 2 == 0 && n2 % 2 == 0)

gcd = k;

k++;

}

I then replaced it with a for loop:

int gcd =1; //initial gcd is 1

for (int k = 2; k <= n1 && k <= k2; k++) {

if (n1 % k == 0 && n2 % k == 0)

gcd = k;

}

Finally, when asked to insert the "/2" into the loop-continuation-condition, I was instructed that this is wrong and was asked why..(in the book)

for (int k =2; k <= n1 / 2 && k <= n2 / 2 ; k++) {

if (n1 % k == 0 && n1 % k == 0)

gcd = k;

For all 3 conditions, when I used the example 125 and 2525, gcd = 25...so this obviously left me wondering why the 3rd set of code was incorrect...however, when I enter 3 and 3 for the 3rd set of code, gcd is 1....it should be 3, correct? Same goes for 2 and 2..gcd should be 2, not 1...Hence my inquiry here...

BTW, Emil, when I take your parameters (n1 = 16 and n2 = 24) into the 3rd set of code, my answer is indeed 8...so there is my nightmare, folks.... isn't this fun?!

Appreciate the assistance everyone.

.....swimming, swimming, swimming.....

Eddie Gerlach wrote:From what I can gather, 'while' these two conditions exist, AND if (n1 % k == 0&&n2 % k == 0), then 'k' is incremented by 1...since it started at 2, shouldn't it then be incremented by 1 and then gcd is 3? However, since this is a Boolean statement that requires the first statement to evaluate as true, and if it doesn't, it ignores the 2nd condition? Then the loop starts anew until a new value is stored for gcd (or 'k') or k becomes >= n1 or n2?

I have a feeling you're overthinking this and getting caught up in the code.

Go back to basics and FORGET about Java: Given two numbers, n1 and n2, what is gcd(n1, n2)? What does it mean?

Why, for example is gcd(24, 16) == 8? Explain it

*in English*.

Now, back to Java. Your starter for 10:

If

`x % y == 0`, and both x and y are integers, what does that mean?

Now, taking that knowledge, go back and look at the algorithm from your second post (the one from your book; not your change), using

`for (int k = 2; k <= n1 && k <= n2; k++) {`(ie, forget the '/2')

What is it trying to do? Try and describe it; if need be, get some paper and pencil and try it out with 16 and 24.

As it happens, the version

*with*the '/2' is very nearly correct. It's missing only a couple of checks (oddly enough, one of the the combinations you tested with is one of them, which actually makes it a very good "corner" case ).

See if you can work out what those checks are.

Winston

Articles by Winston can be found here