Eratosthenes sieve using precomputed primes

Question

I have all the prime numbers that can be stored in 32bit unsigned int and . I want to use them to generate 64-bit primes . using trial division is too slow even when optimized in logic and compilation.

I am trying to modify Sieve of Eratosthenes to work with a predefined list, as shown below:

• in array A from 2 to 4294967291
• in array B from 2 ^ 32 to X inc on 1
• find C which is a multiple of the current prime first.
• from label C and transition from the current primer to X.
• go to 1.

The problem is in step 3, which the module uses to find a simple multiple, such an operation is the reason that I did not use split trails.

Is there a better way to implement step 3 or the whole algorithm.

thanks.

Answer 1

The increment is 2, not 1. The minimum optimization that you should always use is working with coefficients. No need to worry about Evenks.

In C ++, use vector<bool> for a trellised array. It automatically loads into bits.

Pre-calculate the main strokes with a segmented sieve. Then continue to work with large enough segments that fit into your cache, without adding new primes to the main list. For each prime p support an additional long long int value : its current multiple (of course, from a simple square). The step value is two times p in value or the offset p in the array of the lattice, broken down by phases, where the i -th record means that the number o + 2i , o is the least odd not lower than the beginning of the range. There is no need to sort by values ​​of multiple values, the upper limit of the use of the main strokes increases monotonously.

sqrt (0xFFFFFFFFFF) = 1048576 . PrimePi (1048576) = 82025 primes is all you need in the list of main touches. This is peanuts.

The integer arithmetic for long long int should work fine to find modulo and thus the smallest of the many in the range when you first start (or resume your work).

See also the associated answer with pseudo code and another with C code .