Thread: basic prime numbers

I'm willing to bet it is the faster so far and will not be beaten.

Try

Code:

unsigned long j = i * i;

instead of

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

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

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

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.

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.

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

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

Who do you trust more? Your OS or your code?

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.

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.