C++ Prime number task from the book

Question

I'm a C++ beginner ;) How good is the code below as a way of finding all prime numbers between 2-1000:

int i, j;

for (i=2; i<1000; i++) {
  for (j=2; j<=(i/j); j++) {
    if (! (i%j))
      break;
    if (j > (i/j))
      cout << i << " is prime\n";
  }
}

Answer 1

You stop when j = i. A first simple optimization is to stop when j = sqrt(i) (since there can be no factors of a number greater than its square root).

A much faster implementation is for example the sieve of eratosthenes.

Edit: the code looks somewhat mysterious, so here's how it works:

The terminating condition on the inner for is i/j, equivalent to j<i (which is much clearer),since when finally have j==i, we'll have i/j==0 and the for will break.

The next check if(j>(i/j)) is really nasty. Basically it just checks whether the loop hit the for's end condition (therefore we have a prime) or if we hit the explicit break (no prime). If we hit the for's end, then j==i+1 (think about it) => i/j==0 => it's a prime. If we hit a break, it means j is a factor of i,but not just any factor, the smallest in fact (since we exit at the first j that divides i)! Since j is the smallest factor,the other factor (or product of remaining factors, given by i/j) will be greater or equal to j, hence the test. If j<=i/j,we hit a break and j is the smallest factor of i.

That's some unreadable code!