I dont get this specific FOR loop.

I'm having trouble understanding a program that displays all prime numbers between 1 and 100. I know there are many ways of writing this, maybe easier, but I am having trouble understanding this one which is a sample bit of practice code from a book:

Code:

---

#include <iostream>
using namespace std;

int main()
{
int i, j;
bool isprime;

for(i=1; i < 100; i++)
 {
  isprime = true;

for(j=2; j <= i/2; j++)
if((i%j) == 0) isprime = false;
if(isprime)
cout << i << " is prime.\n";
 }
system("PAUSE");
return 0;
}

---

The first For statement, I understand. That goes through all the numbers between 1 & 100.

Code:

---

isprime = true;

---

This statement is used to reset the variable isprime back to true if it was set to false later on in the program.

Code:

---

for(j=2; j <= i/2; j++)

---

This is the statement that I am having trouble with. I'm not sure if its the mathematics that I don't understand or the code itself. Why is it that J is initialised to 2? And what is the condition j<=i/2 for? The other thing I noticed with this statement is that there are no curly braces '{ }' following it. I was under the impression that if the condition in the for statement is true, then there it would execute whatever is in the braces. If its false, it would bypass the content within the braces and execute the next statement outside the braces. But in this example there aren't any braces following it! The first FOR loop does have curly braces following it. Am I missing something here, theoretically?

Code:

---

if((i%j) == 0) isprime = false;

---

My understanding of the above statement is that if the division yields no remainder, set isprime to false

Code:

---

if(isprime)
cout << i << " is prime.\n";

---

The above statement says that if isprime is TRUE, print "<i>is prime"


Can anyone help me understand this? Thanks in advance.

Quote:

---

Originally Posted by fsdama

Why is it that J is initialised to 2?

---

If it were initialized to 1, every number would get sorted out as non-prime because every integral number is divisible by 1, i.e. i &#37; 1 == 0 is always true.

Quote:

---

And what is the condition j<=i/2 for?

---

As you seem to understand for loops as such, you certainly know that this is the loop's terminal condition. There would be more efficient ways to phrase the terminal condition of this loop, but this is one of the more obvious ones.

Imagine a non-prime number j that has the only prime factors 2 and some_large_prime, i.e. is defined as 2 * some_large_prime. Imagine the number would not get sorted out because it is divisible by 2 (which is purely imaginary because it always would, as this is tested first), then the loop would need to run up to j / 2 to find the other prime factor. You get the gist?

The other extreme is a number j that is a square of a prime. In this case the loop would need to run up to at least exactly that prime to find out that j is non-prime. The lowest possible number to which this applies is 4 (== 2 * 2). In this case it is obvious that the loop needs to run up to 2 until it finds out that j is non-prime. In any other case (e.g. 9 == 3 * 3) the loop would need to run up to at least sqrt(j) which is always <= j / 2 for any j >= 4. (If you would look at it the nit-picking way this would mean the code is cheating for any j < 4, but it gets through with that because there is no prime between j / 2 and sqrt(j) in these cases.)

Quote:

---

The other thing I noticed with this statement is that there are no curly braces '{ }' following it.

---

The for loop always controls the next statement or block (enclosed in curly braces) that follows the for statement. If there is only a single statement to be controlled, the braces are redundant (IOW optional). This is a bit less obvious here because the statement to be controlled is an if which in turn controls the statement or block that follows it.

The fact that you ask this question is one of the cases that shows that it's not always recommended to leave out redundant braces, especially if the code is to be understood by beginners. ;)

As for the rest of the program: It looks like you already have perfectly understood what's going on there. :)

Slightly OT, but I always recommend putting in the braces (I am by no means an experienced C++ programmer, but...). Personally I think it makes the code way more readable. Even if you are doing something like:

if ( ... ) { ... }

Where it is all on one line.