Fast algorithm for finding prime numbers? [duplicate]

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

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