Thread: 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...

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.)

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.

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?

Originally Posted by Okane

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.

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