about prime number generation

Hans Åberg haberg-1 at telia.com
Mon May 30 15:24:41 CEST 2022

> On 30 Apr 2022, at 21:12, Garcia Moreno-Esteva, Enrique <enrique.garciamoreno-esteva at helsinki.fi> wrote:
> I need to get primes up to 10^12 (about 2^40), hence my question.

There is a site displaying those, with Java code for various algorithms.

I made a C++ program for the Sieve of Eratosthenes and the Sieve of Atkin, comparing performance:

The Sieve of Atkin takes about 26n ns for n = 10⁴–10⁶ on a 2.4 GHz MPB, about 2.5 times as fast as the (unoptimized) Sieve of Eratosthenes. For higher values of n, it slows down from this linear O(n) behavior, perhaps due to memory issues, about 7 times at 10⁹.

To reach large values like n = 10¹², it suffices to first store a sieve up to √n, and then multiples of that range can be parallelized.

More information about the gmp-discuss mailing list