Fast algorithm for finding prime numbers?

Question

First of all - I checked a lot in this forum and I haven't found something fast enough. I try to make a function that returns me the prime numbers in a specified range. For example I did this function (in C#) using the sieve of Eratosthenes. I tried also Atkin's sieve but the Eratosthenes one runs faster (in my implementation):

public static void SetPrimesSieve(int Range)
    {
        Primes = new List<uint>();
        Primes.Add(2);
        int Half = (Range - 1) >> 1;
        BitArray Nums = new BitArray(Half, false);
        int Sqrt = (int)Math.Sqrt(Range);
        for (int i = 3, j; i <= Sqrt; )
        {
            for (j = ((i * i) >> 1) - 1; j < Half; j += i)
                Nums[j] = true;
            do
                i += 2;
            while (i <= Sqrt && Nums[(i >> 1) - 1]);
        }
        for (int i = 0; i < Half; ++i)
           if (!Nums[i])
                Primes.Add((uint)(i << 1) + 3);
    }

It runs about twice faster than codes & algorithms I found... There's should be a faster way to find prime numbers, could you help me?

Answer 1

When searching around for algorithms on this topic (for project Euler) I don't remember finding anything faster. If speed is really the concern, have you thought about just storing the primes so you simply need to look it up?

EDIT: quick google search found this, confirming that the fastest method would be just to page the results and look them up as needed.

One more edit - you may find more information here, essentially a duplicate of this topic. Top post there states that atkin's sieve was faster than eras' as far as generating on the fly.

Answer 2

Several comments.

1. For speed, precompute then load from disk. It's super fast. I did it in Java long ago.

2. Don't store as an array, store as a bitsequence for odd numbers. Way more efficient on memory

3. If your speed question is that you want this particular computation to run fast (you need to justify why you can't precompute and load it from disk) you need to code a better Atkin's sieve. It is faster. But only slightly.

4. You haven't indicated the end use for these primes. We may be missing something completely because you've not told us the application. Tell us a sketch of the application and the answers will be targetted better for your context.

5. Why on earth do you think something faster exists? You haven't justified your hunch. This is a very hard problem. (that is to find something faster)

Answer 3

You can do better than that using the Sieve of Atkin, but it is quite tricky to implement it fast and correctly. A simple translation of the Wikipedia pseudo-code is probably not good enough.

Answer 4

The fastest algorithm in my experience so far is the Sieve of Erathostenes with wheel factorization for 2, 3 and 5, where the primes among the remaining numbers are represented as bits in a byte array. In Java on one core of my 3 year old Laptop it takes 23 seconds to compute the primes up to 1 billion.

With wheel factorization the Sieve of Atkin was about a factor of two slower, while with an ordinary BitSet it was about 30% faster.

See also this answer.

Answer 5

See this article for learning about prime numbers, you can also find code in TopCoder, prime numbers fast algorithms are more complicated than common algorithm, the basic idea is to guess number is prime or not (in O(1) or at most O(log(n))) the algorithms always return a good answer, if the number is probably prime then check it with algorithm like your algorithm. See IsolatedPrime problem in topcoder.com. one of test method is Miller Rabin Algorithm also see this