Sieve of Eratosthenes using precalculated primes

Question

I've all prime numbers that can be stored in 32bit unsigned int and I want to use them to generate some 64bit prime numbers. using trial division is too slow even with optimizations in logic and compilation.

I'm trying to modify Sieve of Eratosthenes to work with the predefined list, as follow:

1. in array A from 2 to 4294967291
2. in array B from 2^32 to X inc by 1
3. find C which is first multiple of current prime.
4. from C mark and jump by current prime till X.
5. go to 1.

The problem is step 3 which use modulus to find the prime multiple, such operation is the reason i didn't use trail division.

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

thank you.

Answer 1

Increment by 2, not 1. That's the minimal optimization you should always use - working with odds only. No need to bother with the evens.

In C++, use vector<bool> for the sieve array. It gets automatically bit-packed.

Pre-calculate your core primes with segmented sieve. Then continue to work by big enough segments that fit in your cache, without adding new primes to the core list. For each prime p maintain additional long long int value: its current multiple (starting from the prime's square, of course). The step value is twice p in value, or p offset in the odds-packed sieve array, where the i-th entry stands for the number o + 2i, o being the least odd not below the range start. No need to sort by the multiples' values, the upper bound of core primes' use rises monotonically.

sqrt(0xFFFFFFFFFF) = 1048576. PrimePi(1048576)=82025 primes is all you need in your core primes list. That's peanuts.

Integer arithmetics for long long ints should work just fine to find the modulo, and so the smallest multiple in range, when you first start (or resume your work).

See also a related answer with pseudocode, and another with C code.