Quick question, for statement with a break

Discussion in 'Mac Programming' started by cybrscot, Feb 6, 2011.

  1. cybrscot macrumors 6502

    cybrscot

    Joined:
    Dec 7, 2010
    Location:
    Somewhere in Southeast Asia
    #1
    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):

    Code:
    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
     
  2. lee1210, Feb 6, 2011
    Last edited: Feb 6, 2011

    lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #2
    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.
     
  3. cybrscot thread starter macrumors 6502

    cybrscot

    Joined:
    Dec 7, 2010
    Location:
    Somewhere in Southeast Asia
    #3
    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??
     
  4. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #4
    Code:
    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
     
  5. balamw Moderator

    balamw

    Staff Member

    Joined:
    Aug 16, 2005
    Location:
    New England
    #5
    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
     
  6. cybrscot thread starter macrumors 6502

    cybrscot

    Joined:
    Dec 7, 2010
    Location:
    Somewhere in Southeast Asia
    #6
    Yes Squirt is that refreshing lemon-lime drink! Had it back in the states when was younger! :D
     
  7. Detrius macrumors 68000

    Joined:
    Sep 10, 2008
    Location:
    Asheville, NC
    #7
    Yes, the square root would be enough. It's the largest possible divisor that wouldn't need to be multiplied by something smaller.
     
  8. Sydde macrumors 68020

    Sydde

    Joined:
    Aug 17, 2009
    #8
    So if you enclosed the entire loop within the for block
    Code:
    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?
     
  9. chown33 macrumors 604

    Joined:
    Aug 9, 2009
    #9
    Most free compilers would probably make the call every time. That seems like the kind of optimization you'd have to pay money for.

    Code:
    for(d=2,e=sqrt(n);(d<e)&&(n%d);++d);
    Becausespacesaresuboptimal.</kidding>
     
  10. Sydde macrumors 68020

    Sydde

    Joined:
    Aug 17, 2009
    #10
    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…
    ;)
     
  11. Catfish_Man macrumors 68030

    Catfish_Man

    Joined:
    Sep 13, 2001
    Location:
    Portland, OR
    #11
    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.
     
  12. gnasher729 macrumors P6

    gnasher729

    Joined:
    Nov 25, 2005
    #12
    It doesn't really matter, because it is incorrect anyway. Check n = 4.
     
  13. Sydde macrumors 68020

    Sydde

    Joined:
    Aug 17, 2009
    #13
    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.
     
  14. balamw Moderator

    balamw

    Staff Member

    Joined:
    Aug 16, 2005
    Location:
    New England
    #14
    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

    Code:
    d <= sqrt(n)
    B
     

Share This Page