Fast algorithm for finding prime numbers?

Question

First of all - I checked a lot on this forum, and I did not find something fast enough . I am trying to make a function that returns me primes in the specified range. For example, I made this function (in C #) using an Eratosthenes sieve. I also tried the Atkin sieve, but Eratosthenes is 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 works about twice as fast as the codes and algorithms I found ... There must be a faster way to find primes, could you help me?

Answer 1

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

EDIT: A quick search on the this search engine, confirming that the fastest method would be to simply display the results and search for them as needed.

Another edit - here you can find more detailed information, basically a duplicate of this topic. The top column says that the sieve with the atkin was faster than the eras, before being generated on the fly.

Answer 2

The fastest algorithm in my experience so far is a sieve of eratostenes with factorization of wheels for 2, 3 and 5, where prime numbers among the remaining numbers are represented as bits in an array of bytes. In Java, it takes 23 seconds on a single core of my 3 year old laptop to calculate prime numbers up to 1 billion.

When factorizing the wheels, the Atkin sieve was about two times slower, and with the usual BitSet it was about 30% faster.

See also this answer .

Answer 3

I made an algorithm that can find primes from the range of 2-90,000,000 in 0.65 seconds on a 350M laptop written in C .... you need to use bitwise operations and have a “code” to recalculate your array index so that index the specific bit you want. for example, if you want the folds of number 2, specific bits will be, for example ... 10101000 ... so if you read on the left ... you get an index of 4,6,8 ... thats it

Answer 4

A few comments.

• For speed, pre-copy, then boot from disk. It is super fast. I have done this in Java a long time ago.

• Do not store as an array, store as a bit sequence for odd numbers. The method is more efficient in working with memory.

• If your speed issue is that you want this particular calculation to be fast (you need to justify why you cannot precompile and load it from disk), you need to code the best Atkin sieve. It's faster. But just a little bit.

• You did not specify the end use of these primes. Perhaps we are missing something because you did not tell us the application. Tell us a sketch of the application, and the answers will be better targeted to your context.

• Why do you think something faster exists? You have not justified your guess. This is a very difficult problem. (i.e. find something faster)

Answer 5

You can do better than using Sieve Atkin , but it’s quite difficult to implement it quickly and correctly. A simple translation of the Wikipedia pseudocode is probably not good enough.