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?

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

Solution 2

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.

Solution 3

I did an algorithm that can find prime numbers from range 2-90 000 000 for 0.65 sec on I 350M-notebook, written in C .... you have to use bitwise operations and have "code" for recalculating index of your array to index of concrete bit you want. for example If you want folds of number 2, concrete bits will be for example ....10101000 ... so if you read from left ... you get index 4,6,8 ... thats it

Comments

[Gabe]

There are 50M primes less than 10^9, so precomputing them would give you a 200MB table. It would actually be smaller to just store the sieve (10^9 bits is 125MB, and you don't need to store the even bits, so you could fit it all in under 64MB).

[Gleno]

In what range are you looking for primes? Just between 0 and max int? Also how wide is the range?

[Ohad]

no, those aren't fast, even my code is faster. I really saw something that says it's very fast(somewhy I don't trust it...) I'll check it tommorow, I have to go. thanks anyway. (it's not duplicate of the other topic, there were slow answers)

[Ohad]

yea, I tried to do the sieve of atkins... my array contained also even numbers but I didn't touch them... it was 1.5 times slower than the eroathenes sieve. (most of the codes I found were doubled from my eroa). and of course - I used even primes properties and let's say I know to do optimization... but it's still slower (there are unsused bytes in my array... that shouldn't matter).

[Landei]

Why don't show you this code as well?

[Olathe]

A very fast C implementation from one of the authors of the paper that describes it is at cr.yp.to/primegen.html

[Nick Larsen]

That is an awesome article, +1

[Saeed Amiri]

there are algorithms very very faster than this simple one, see my answer

[Beezer]

Testing for a prime is such a bore, that I completely agree with jlv...simply store and look it up. In fact, there should be a free global webservice that is cached globally, that can provide the answers...or better still, java should store all primes to max int in a lookup; in the Docker world there should be an image with an application that provides a range of services around primes including lookup. Its simply such a bore to have to test it, and then look for the most performant method in whatever your language of choice is.