macOS Quick question, for statement with a break

[cybrscot]

I know a for loop has the form..

for (expr1 ; expr2; expr3) statement

The loop body is the statement, correct?

my book shows this example

Suppose we're writing a program that checks whether a number is prime. Our plan is to write a for stmt that divides n by the numbers between 2 and - 1. We can break out of the loop as soon as any division is found, there's no need to try the remaining possibilities. After the loop has terminated, we can use an if statement to determine whether termination was premature (hence n isn't prime) or nomal (n is prime):

for(d = 2 ; d <  n; d++)
    if (n % d ==0) break ;
if (d < n)
    printf ("%d is divisible by %d\n", n, d) ;
else
    printf ("%d is prime\n", n) ;

The book says that the break is useful for writing loops that exit in the middle of the body rather than at the beginning or end. But in the above example, isn't the loop body the statement if (n %d ==0) ??? If so, how can it be considered that the break is exiting in the middle of the loop? It appears to me that the loop is terminated because break comes after the complete statement.

Of course I'm probably wrong and the book is right, but why? That's the way it looks to me. I don't see a compound statement up there, it would have to be separated by commas.
Thanks

 

[lee1210]

The if expression includes the statement executed if true. In any event, just always have the statement that is the body of a flow control structure be a block {}, then you aren't guessing.

Also, no need to go to n-1, just go to n/2.

-Lee

Edit: as an aside, there are those that frown on break, because it breaks the condition of the control structure. That is, when the loop exits via break you don't know for sure that the condition under which the loop should exit has actually been falsified. In this case, obviously that behavior is depended on. An alternative is to add, for example, a divisorFound, and add && !divisorFound to the condition of the for. Then when the if is true, set divisorFound to true. Then your loop exits cleanly and you have a variable to check to see if a divisor was found rather than mucking around with loop control variables outside the loop.

This is a matter of style. Sometimes a break makes your code much more elegant, sometimes it just muddies your logic. I try to avoid zealotry, so I'll just provide both sides and let you decide what suits you best. Just remember that when you're working with others standards may exist that force you to modify your style unless you can sell the team on your way and you're going to fix up existing code to fit.

 

[cybrscot]

The if expression includes the statement executed if true. In any event, just always have the statement that is the body of a flow control structure be a block {}, then you aren't guessing.

Also, no need to go to n-1, just go to n/2.

-Lee

Thanks Lee, the code was straight from the book. So I guess I'm not exactly sure where the {} would go if I was putting them in there. Also, I forgot to mention that I wasn't sure even what they mean when they say divide n by the numbers between 2 and n - 1. Yes, I understand the 2. But with the n - 1 are they saying to divide n (which I assume is the user input), by itself minus 1? Example, I enter 6. Are we dividing 6 by 5??

 

[lee1210]

Thanks Lee, the code was straight from the book. So I guess I'm not exactly sure where the {} would go if I was putting them in there. Also, I forgot to mention that I wasn't sure even what they mean when they say divide n by the numbers between 2 and n - 1. Yes, I understand the 2. But with the n - 1 are they saying to divide n (which I assume is the user input), by itself minus 1? Example, I enter 6. Are we dividing 6 by 5??

for(d = 2 ; d <  n; d++) {
  if (n % d ==0) {
    break ;
  }
}
if (d < n) {
  printf ("%d is divisible by %d\n", n, d) ;
} else {
  printf ("%d is prime\n", n) ;
}

This way you clearly recognize what code belongs with which loop or conditional, and you can easily add statements if needed.

The book meant that for a number n, test to see if it can be evenly divided by any number from 2 to n - 1. So for an n of 6, you'd test 2,3,4,5. I was saying that you could just test 2 and 3, because it's impossible for a number to be evenly divisible by anything greater than one half of itself (other than the number itself).

-Lee

 

[balamw]

Also, no need to go to n-1, just go to n/2.

Wouldn't sqrt(n) be enough? (I know cybrscot probably hasn't been introduced to sqrt yet, but still).

If it's divisible by (n/2) it would also be divisible by 2.

B

 

[cybrscot]

Wouldn't sqrt(n) be enough? (I know cybrscot probably hasn't been introduced to sqrt yet, but still).

If it's divisible by (n/2) it would also be divisible by 2.

B

Yes Squirt is that refreshing lemon-lime drink! Had it back in the states when was younger!

 

[Detrius]

Wouldn't sqrt(n) be enough? (I know cybrscot probably hasn't been introduced to sqrt yet, but still).

If it's divisible by (n/2) it would also be divisible by 2.

B

Yes, the square root would be enough. It's the largest possible divisor that wouldn't need to be multiplied by something smaller.

 

[Sydde]

So if you enclosed the entire loop within the for block

for ( d = 2 ; ( d < sqrt( n ) )&&( n % d != 0 ) ; d++ ) ;

does sqrt( n ) get calculated on every pass of the loop, or will the compiler set it up to calculate the value just the one time?

 

[chown33]

So if you enclosed the entire loop within the for block

for ( d = 2 ; ( d < sqrt( n ) )&&( n % d != 0 ) ; d++ ) ;

does sqrt( n ) get calculated on every pass of the loop, or will the compiler set it up to calculate the value just the one time?

Most free compilers would probably make the call every time. That seems like the kind of optimization you'd have to pay money for.

for(d=2,e=sqrt(n);(d<e)&&(n%d);++d);

Becausespacesaresuboptimal.</kidding>

 

[Sydde]

Most free compilers would probably make the call every time. That seems like the kind of optimization you'd have to pay money for.

for(d=2,e=sqrt(n);(d<e)&&(n%d);++d);

Becausespacesaresuboptimal.</kidding>

I seem to recall once writing a while loop that did not seem to respond to changes in one of the variables used for its condition, but I don't remember what was causing the problem or how I fixed it. Since that time, I have found it better to spread code out into the biggest, most verbose form because it makes single-stepping more useful, and ultimately gcc (using XCode's default settings) squeezes it down into what I probably would have written in the first place.

Though I would never use "e" as a variable name, since that is the nl constant 2.71828…

 

[Catfish_Man]

Most free compilers would probably make the call every time. That seems like the kind of optimization you'd have to pay money for.

GCC and LLVM will both hoist constant math expressions, as far as I know. GCC 4.2 might not for some exotic ones, I forget when MPFR was integrated.

 

[gnasher729]

So if you enclosed the entire loop within the for block

for ( d = 2 ; ( d < sqrt( n ) )&&( n % d != 0 ) ; d++ ) ;

does sqrt( n ) get calculated on every pass of the loop, or will the compiler set it up to calculate the value just the one time?

It doesn't really matter, because it is incorrect anyway. Check n = 4.

 

[Sydde]

It doesn't really matter, because it is incorrect anyway. Check n = 4.

Why is that incorrect? The loop exits when it encounters a factor, so it is exiting correctly even though the exit is based on the first test.

 

[balamw]

Why is that incorrect? The loop exits when it encounters a factor, so it is exiting correctly even though the exit is based on the first test.

I think the problem case is actually 9, 25, 49, ... (or any square of a prime number)

For n=9, sqrt(9)= 3 and you don't include it (d < 3) it will incorrectly conclude that 9 is prime. It needs to be

d <= sqrt(n)

B