tags:

views:

287

answers:

4

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";
  }
}
+9  A: 

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!

Mau
Can you explain j=i since I have the condition of (j>(i/j))
What does it mean after all ( j > ( i / j ) ) ??
So I guess you didn't write the code? Which looks like it was written by someone trying to look smart anyway :) No matter, added explanation above.
Mau
Herbert Schildt wrote it :)
@Mau: Hey friend; explain me this: Why doesn't 1st >if< break the condition after !(i%j). If you put cout<<i between the two if's you'll see that the only condition that decides which num is prime is -> j > (i/j)
@persistent: Herbert Schildt has written some very bad books in his time, one of which earned the nickname "bullschildt". If this is the kind of example code he gives then I don't think he's improved much.
Mike Seymour
A: 

Not very good. In my humble opinion, the indentation and spacing is hideous (no offense). To clean it up some:

int i, j;

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

This reveals a bug: the if (j > i/j) ... needs to be on the outside of the inner loop for this to work. Also, I think that the i/j condition is more confusing (not to mention slower) than just saying j < i (or even nothing, because once j reaches i, i % j will be 0). After these changes, we have:

int i, j;

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

This works. However, the j > i/j confuses the heck out of me. I can't even figure out why it works (I suppose I could figure it out if I spent a while looking like this guy). I would write if (j == i) instead.

What you have implemented here is called trial division. A better algorithm is the Sieve of Eratosthenes, as posted in another answer. A couple things to check if you implement a Sieve of Eratosthenes:

  1. It should work.
  2. It shouldn't use division or modulus. Not that these are "bad" (granted, they tend to be an order of magnitude slower than addition, subtraction, negation, etc.), but they aren't needed, and if they're present, it probably means the implementation isn't really that efficient.
  3. It should be able to compute the primes less than 10,000,000 in about a second (depending on your hardware, compiler, etc.).
Joey Adams
@Joey Adams: j > i/j is the same as j*j > i, except for rounding error. No composite number i has a least divisor which is greater than sqt(i), which is why this works.
Jørgen Fogh
Tell that to Herbert Schildt... it's from the book C++ from the ground up 3rd
@Jørgen Fogh Can you please explain your statement on some example ;)thx
@persistent: 100 can be factored as 2 * 50, and sqrt(100) = 10. It's no use searching for factors above 10; they correspond to the factors you already found below sqrt(100).
Michael Foukarakis
@mfukar >10 = "they correspond to the factors you already found below sqrt(100)" here I'm little confused
" No composite number i has a least divisor which is greater than sqt(i), which is why this works" I don't understand, what about 27 --> 9 > sqrt(27)and 9 is a factor of 27
A: 

First off, your code is both short and correct, which is very good for at beginner. ;-)

This is what I would do to improve the code:

1) Define the variables inside the loops, so they don't get confused with something else. I would also make the bound a parameter or a constant.

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

2) I would use the Sieve of Eratosthenes, as Joey Adams and Mau have suggested. Notice how I don't have to write the bound twice, so the two usages will always be identical.

#define MAX 1000
bool prime[MAX];
memset(prime, sizeof(prime), true);
for(int i=4;i<MAX;i+=2) prime[i] = false;
prime[1] = false;
cout<<2<<" is prime\n";
for(int i=3;i*i<MAX;i+=2)
    if (prime[i]) {
        cout<<i<<" is prime\n";
        for(int j=i*i;j<MAX;j+=i)
            prime[j] = false;
    }

The bounds are also worth noting. i*i<MAX is a lot faster than j > i/j and you also don't need to mark any numbers < i*i, because they will already have been marked, if they are composite. The most important thing is the time complexity though.

3) If you really want to make this algorithm fast, you need to cache optimize it. The idea is to first find all the primes < sqrt(MAX) and then use them to find the rest of the primes. Then you can use the same block of memory to find all primes from 1024-2047, say, and then 2048-3071. This means that everything will be kept in L1-cache. I once measured a ~12 time speedup by using this optimization on the Sieve of Eratosthenes.

You can also cut the space usage in half by not storing the even numbers, which means that you don't have to perform the calculations to begin working on a new block as often.

If you are a beginner you should probably just forget about the cache for the moment though.

Jørgen Fogh
The original code is not correct. Try running it. It repeats answers, and it skips 2. Why don't people test things?
Joey Adams
A: 

The one simple answer to the whole bunch of text we posted up here is : Trial division! If someone mentioned mathematical basis that this task was based on, we'd save plenty of time ;)