Amazon.com Widgets Stuck on Program 6.10 (Prime numbers) if anyone has any time to help explain...
Welcome, Guest. Please login or register.
Did you miss your activation email?
April 24, 2014, 03:25:41 PM
Home Help Search chat Login Register 
News: Read this please.The Great Kangaroo Escape Looking for reviews of the 4th ed on Amazon!   Twitter:  @skochan
                     

+ Official Forum for Programming in Objective-C (the iPhone Programming Language) - Stephen Kochan
|-+ Old Stuff
| |-+ Chapter Study
| | |-+ Chapter 6 - Making Decisions
| | | |-+ Stuck on Program 6.10 (Prime numbers) if anyone has any time to help explain...
Pages: [1] Go Down
Print
Author Topic: Stuck on Program 6.10 (Prime numbers) if anyone has any time to help explain... (Read 1528 times)
ChrisJS
Newbie
*
Posts: 5






on: August 18, 2009, 08:13:18 PM

/* Program 6.10 (Page 124, Programming in Objective-C 2.0 Second Edition, Addison Wesley)

I don't really understand the way this program is explained in the book.

Could anyone explain the theory behind this?

Output is below the program code (code has been modified a bit)...
*/




#include <stdio.h>
main() {
int p, d, isPrime, remainder; //note: added variable remainder, just to use with printf

    for (p = 2; p <= 11; ++p) {
        isPrime = 1;

        for(d = 2; d < p; ++d) {
            remainder = p % d;
            if (remainder == 0)
                isPrime = 0;
            printf("\n   inner: %i %i remainder: %i", p,d,remainder); //inner if
        }

        printf("\nouter: %i %i remainder: %i", p,d,remainder); //outer if
        if (isPrime != 0)
        printf("\n---------------------------Prime: %i",p);
    }
}





/* OUTPUT:

outer: 2 2 remainder: 2621256
---------------------------Prime: 2
   inner: 3 2 remainder: 1
outer: 3 3 remainder: 1
---------------------------Prime: 3
   inner: 4 2 remainder: 0
   inner: 4 3 remainder: 1
outer: 4 4 remainder: 1
   inner: 5 2 remainder: 1
   inner: 5 3 remainder: 2
   inner: 5 4 remainder: 1
outer: 5 5 remainder: 1
---------------------------Prime: 5
   inner: 6 2 remainder: 0
   inner: 6 3 remainder: 0
   inner: 6 4 remainder: 2
   inner: 6 5 remainder: 1
outer: 6 6 remainder: 1
   inner: 7 2 remainder: 1
   inner: 7 3 remainder: 1
   inner: 7 4 remainder: 3
   inner: 7 5 remainder: 2
   inner: 7 6 remainder: 1
outer: 7 7 remainder: 1
---------------------------Prime: 7
   inner: 8 2 remainder: 0
   inner: 8 3 remainder: 2
   inner: 8 4 remainder: 0
   inner: 8 5 remainder: 3
   inner: 8 6 remainder: 2
   inner: 8 7 remainder: 1
outer: 8 8 remainder: 1
   inner: 9 2 remainder: 1
   inner: 9 3 remainder: 0
   inner: 9 4 remainder: 1
   inner: 9 5 remainder: 4
   inner: 9 6 remainder: 3
   inner: 9 7 remainder: 2
   inner: 9 8 remainder: 1
outer: 9 9 remainder: 1
   inner: 10 2 remainder: 0
   inner: 10 3 remainder: 1
   inner: 10 4 remainder: 2
   inner: 10 5 remainder: 0
   inner: 10 6 remainder: 4
   inner: 10 7 remainder: 3
   inner: 10 8 remainder: 2
   inner: 10 9 remainder: 1
outer: 10 10 remainder: 1
   inner: 11 2 remainder: 1
   inner: 11 3 remainder: 2
   inner: 11 4 remainder: 3
   inner: 11 5 remainder: 1
   inner: 11 6 remainder: 5
   inner: 11 7 remainder: 4
   inner: 11 8 remainder: 3
   inner: 11 9 remainder: 2
   inner: 11 10 remainder: 1
outer: 11 11 remainder: 1
---------------------------Prime: 11
Process returned 0 (0x0)   execution time : 0.064 s


It seems like once the second (inner) for loop is executed it continues as stated, until the
condition d<p is met.  What I don't understand about this is that it seems the end
remainder of isPrime in the loop is ALWAYS 1, yet the prime isn't always printed, and according
to the last statement:

if (isPrime != 0)
printf("\n---------------------------Prime: %i",p);

it should be printed every time.
*/
Logged
rgronlie
Global Moderator
Full Member
*****
Posts: 212







Reply #1 on: August 18, 2009, 11:39:17 PM

Try stepping through your code line by line using the debugger.

If you follow the program execution you'll see that when d == p the program leaves the inner loop and remainder is left unchanged from the previous cycle through the loop.

This is also why the first remainder is some weird number. Because remainder hasn't been initialized to 0.
Logged

Sanity: Minds are like parachutes. Just because you've lost yours doesn't mean you can borrow mine.
ChrisJS
Newbie
*
Posts: 5






Reply #2 on: August 19, 2009, 09:13:49 AM

Try stepping through your code line by line using the debugger.

If you follow the program execution you'll see that when d == p the program leaves the inner loop and remainder is left unchanged from the previous cycle through the loop.

This is also why the first remainder is some weird number. Because remainder hasn't been initialized to 0.


Thank you, I can see that as it's listed in the output, but that's not what I was wondering about.  If you look at the output again, remainder never == 0 at the end of the inner loop, so isPrime can never == 0.  Correct?  So the last printf should always print, no?

I just don't understand the theory behind this math/code either.  How it's finding out which are primary numbers.

Thanks for your time rgronlie

----EDIT----
Oh I finally got it.  It's simple, but I had to read it through about 5 times... I'm a little slow on some things I guess!

So, if p % d == 0 even once through that loop, the rest of the loop doesn't even matter, because the 0 means the number is not prime (since 0 remainder means it's evenly divisible).  The loop just follows through anyways.

When prime is set to 0, the number is not prime because of this and isPrime is once again set to 1 at the start of the outer loop.
Last Edit: August 19, 2009, 09:39:54 AM by ChrisJS Logged
rgronlie
Global Moderator
Full Member
*****
Posts: 212







Reply #3 on: August 19, 2009, 09:40:50 AM

Quote
If you look at the output again, remainder never == 0 at the end of the inner loop, so isPrime can never == 0.  Correct?  So the last printf should always print, no?

No that is not correct. If you look at your output you'll see that remainder has == 0 at some point for non-prime numbers. isPrime is set to 0 whenever there is a remainder of 0. It doesn't get set back to 1 until the next time through the outer loop.

From Wikipedia:
Quote
In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself... The number 1 is by definition not a prime number.

The outer loop selects the number to test.

The inner loop divides that number by all numbers from 2 and up to (but not including) the number being tested. If at any time there is a remainder of 0 then the number is not a prime number.
Logged

Sanity: Minds are like parachutes. Just because you've lost yours doesn't mean you can borrow mine.
ChrisJS
Newbie
*
Posts: 5






Reply #4 on: August 19, 2009, 10:35:27 AM

Thanks again rgronlie,

I think, because the inner loop is not terminated upon finding a zero remainder, it was confusing me.  Maybe I was the only one confused by this but I think it would have been easier to understand, since we've already learned about it:


#include <stdio.h>
main() {
int p, d, isPrime;

    for (p = 2; p <= 11; ++p) {

        for(d = 2, isPrime = 1; d < p; ++d) {
            if (p % d == 0) {
                isPrime = 0;
               break;
            }
        }

        if (isPrime != 0)
        printf("\nPrime: %i",p);
    }
}
Logged
Pages: [1] Go Up
Print
Jump to:



Login with username, password and session length

Powered by MySQL Powered by PHP Powered by SMF 1.1.11 | SMF © 2006-2009, Simple Machines LLC Valid XHTML 1.0! Valid CSS!
Entire forum contents (c) 2009 classroomM.com. All rights reserved.