# basic prime numbers

This is a discussion on basic prime numbers within the C++ Programming forums, part of the General Programming Boards category; I'm willing to bet it is the faster so far and will not be beaten. Try Code: unsigned long j ...

1. I'm willing to bet it is the faster so far and will not be beaten.
Try
Code:
`unsigned long j = i * i;`
Code:
`unsigned long j = (i << 1);`

You could also treat 2 as a special case and ignore even numbers altogether (both in looping and output).

2. > Do your four levels of brace-less control statements also contribute to the optimization, or is that just obfuscation?

Ha ha. Just for confusion. I'm sorry. I just like to leave braces out in my personal code because I think it makes it easier to see nested loops.

>This algorithm is called the Sieve of Erastothenes, by the way.

Thanks. I couldn't think of the name to save my life.

To anon:
Code:
`unsigned long j = i * i;`
is not the same as
Code:
`unsigned long j = (i << 1);`
Shifting by one is *maybe* an optimization to multiplying by 2. I can't prove that it is actually faster in practice. As far as ignoring even numbers, I think that somewhere I would need a loop to ignore them anyway but it's possible that if you stored the primes differently, you could avoid that loop.

3. Look closer. I'm not multiplying by 2, I'm squaring i. If the numbers get very high, this can skip a lot of unnecessary looping, because no multiple of i less than i squared is going to be a prime. (It makes your code a bit faster.)

4. I would do the special case for two, and use a vector<bool> containing only the results for odd numbers which would cut the memory usage down to one-sixteenth.

5. Originally Posted by anon
Look closer. I'm not multiplying by 2, I'm squaring i. If the numbers get very high, this can skip a lot of unnecessary looping, because no multiple of i less than i squared is going to be a prime. (It makes your code a bit faster.)
Ah hah! Indeed it does make the algorithm faster.

6. I think it is kind of funny. you optimize the code, but after all that you forget to free the memory.
maybe
Code:
`delete []primes;`
before the return statement?

7. I know it's good practice and all, but doesn't the operating system release anything you have allocated upon exit anyways?

8. I know it's good practice and all, but doesn't the operating system release anything you have allocated upon exit anyways?

9. Personally I think since the OS is coded by people just the same as us there can easily be mistakes, so I would like to be sure. Maybe the OS does return it, but I think the precaution cant hurt. Also, if the OS returned memory every time, we would not have memory leaks would we?

10. Umm ... actually, the way the system works, it's completely impossible for the OS not to return the memory.

But only when the program ends! And if this snippet doesn't free the memory but rather relies on the OS, because "the program ends immediately afterwards anyway", then you will get a memory leak the moment you later take this snippet and make it part of a bigger program.

11. Originally Posted by CornedBee
Umm ... actually, the way the system works, it's completely impossible for the OS not to return the memory.

But only when the program ends! And if this snippet doesn't free the memory but rather relies on the OS, because "the program ends immediately afterwards anyway", then you will get a memory leak the moment you later take this snippet and make it part of a bigger program.
Impossible for Window perhaps, but not impossible for every platform under the sun.

That last part is certainly the gotcha, using code with a leak repeatedly will surely spell trouble.

Page 3 of 3 First 123