Simple Prime # code --- Please help

This is a discussion on Simple Prime # code --- Please help within the C Programming forums, part of the General Programming Boards category; Hey there... I'm new to C and this forum, I'm going through Learn C on a Mac by Mark Davis. ...

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    3

    Simple Prime # code --- Please help

    Hey there... I'm new to C and this forum, I'm going through Learn C on a Mac by Mark Davis. In his book he has this code to search for prime numbers between 1 and 100. The code works, its just that I don't really understand why and its driving me crazy!!!!! I don't know what I'm missing.
    Here's the code,

    headers.....
    Code:
    printf("Prime numbers from 1 to 100 are, 2,");
    for(candidate=3;candidate<=100;candidate+=2){
    	isPrime=true
    	last=sqrt(candidate);
    	for(i=3:(i<=last) && isPrime;i+=2){
    		if((candidate%i) == 0)
    		isPrime=false
    	}
    	if(isPrime)
    		printf("%d,",candidate);
    }
    return 0;
    }

    In the second for he has i=3 (initialization) and i<=last && isPrime (termination). On the first run, if the cadidate is 3 and i=3 then the sqrt(3) will never be bigger than 3(candidate)....What am I missing??????
    Thank you in advance for your help...

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Given that that's how it's supposed to work, nothing at all. (Since the termination condition is true right away, the for loop doesn't run.)

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    An odd number is not a prime number if it has a number of at least 3 and less than or equal to the square root of the number that divides it. Since it's odd, 2 doesn't divide it, so per definition of a prime number an odd number that is not prime has a divisor from 3 to the square root of the number, inclusive.
    Why the square root? Let's say an integer x has a divisor greater than the square root, n. Then x/n must be an integer that also divides x. And since n > sqrt(x), x/n < sqrt(n), so x/n would be a divisor of x less than the square root.

    But for 3, the loop doesn't run, no. Because there is no integer less than 3 that might divide it.

  4. #4
    Registered User
    Join Date
    Apr 2010
    Posts
    3
    Wow...thanks for the quick response....but I still don't get why when I run the code it spits out 2,3,5,7,11 etc... why is it giving me 3 and 5 and 7 which still have sqrts smaller than 3?

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Okane View Post
    Wow...thanks for the quick response....but I still don't get why when I run the code it spits out 2,3,5,7,11 etc... why is it giving me 3 and 5 and 7 which still have sqrts smaller than 3?
    isPrime=true

    means what it says, so those numbers are prime unless the loop says otherwise.

  6. #6
    Registered User
    Join Date
    Apr 2010
    Posts
    3
    ohhhhh, FINALLY...THANKS!!!! this was killing me...I see it now. If the second for doesn't execute then isPrime is true and therefor a prime number!!
    Thank you very much

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 18
    Last Post: 11-04-2005, 01:41 PM
  2. << !! Posting Code? Read this First !! >>
    By biosx in forum C++ Programming
    Replies: 1
    Last Post: 03-20-2002, 11:51 AM
  3. Here is my prime code! why wont it work?
    By cprogramnewbie in forum C Programming
    Replies: 4
    Last Post: 03-10-2002, 02:53 AM
  4. Simple Code, looking for input.
    By Alien_Freak in forum C Programming
    Replies: 3
    Last Post: 03-03-2002, 10:34 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21