prime numbers

[Pritpal singh]

to print the list of prime numbers between natural numbers "1" to "n" we have that "sqrt(n)" algorithm. is there any other algorithm so that the compiler takes even lesser time?????

[Karql]

Hi.

You can a bit optimize Sito Erastotenes algorithm.

2 is the only one even number, so you can increase counter not by 1 but by 2.
You also havn't reset even number twice times.

This version of algorith is about 2x faster than normal.
Is it good enough for you?

#include <cmath>

const int MAX = 1000000;
int P[MAX];

int main()
{
        int i, p, j;

        P[2] = 2;
        for ( i = 3; i < MAX; i += 2 )
        {
                P[i] = i;
        }


        for ( i = 3, p = sqrt(MAX); i <= p; i += 2 )
        {
                if ( P[i] != 0 )
                {
                        for ( j = i * i; j <= MAX; j = j + 2 * i )
                        {
                                P[j] = 0;
                        }
                }
        }

        return 0;
}

[Scipio]

http://en.wikipedia.org/wiki/Primality_test

Wikipedia is often a good place to look for algorithm :)

[jsmith]

The Sieve of Eratothenes is probably one of the faster "simple" algorithms, though its primary drawback is that it requires storage of all primes less than N which means it does not scale to larger values of N.

Otherwise all you can do is optimize the above code.

One thing to do is move the calculation of sqrt(MAX) outside the for() loop since sqrt() will be called every time through the loop even though the result never changes.

[EDIT: never mind on the last statement, I just realized you already did this by precomputing sqrt(MAX) in the initializer.]

[jsmith]

In terms of memory usage, all you really need is a boolean array to indicate whether or not the number is prime. That would reduce your memory utilization by a factor of 4, although that might not speed things up at all since now you will be performing non-aligned accessed.

And you could further reduce memory utilization (by a factor of 8) by using a bitset, although now each bit access requires a multiplication, mod, and addition, so that will certainly be slower.