Generating prime numbers up to 1018

Jorge Teran: jteran@umsa.bo
|

- Prime programs

- Download prime Numbers

Purpose of this page

This page summarizes my concern of reviewing the generation of prime numbers and how to eliminate the limitations of memory, showing the use of a segmented sieve.

This page was developed for educational purpose only.

What is a prime number?

A prime number is a positive integer greater than 1, that his only factors are 1 or it's self

A prime counting funtion is one that counts the number of prime numbers less or equal to an number n, normally referred to as π(n).

There are many methods to know if a number is prime, the trivial method is to divide by all the previous prime numbers up to the square root of n.

To verify if a number is prime takes a very long time so it is necessary to look for an alternative method.

Sieve of Eratostenes

Eratosthenes of Cyrene born c. 276 BC was a Greek mathematician that invented this sieve to generate and determine if a number is prime.

This method works in the following way:

  • First we write a list with all the numbers starting from 2 to n
  • Second, we start with number 2 and mark all numbers
  • which are multiples of 2.
  • Third, continue with the following numbers until you reach the square root of n
All unmarked numbers are prime numbers.

This method is one of the fastest ways to generate prime number, with the problem that you will need enough memory to enumerate all the numbers. This can be solved using a segmented sieve. The approach developed is described the link to the program. A more efficient sieve is the Atkins, but it was not considered here.

The Eratosthenes sieve allows to compute primes up to 22,004,878,992. in only 174 seconds using a pentium i5 notebook. The segmented sieve program can generate 1010 numbers in a previous defined segment in only 22 seconds In the page this program can be downloaded without any warranty and used for non commercial use.

For prime numbers up to 1010 they can be generated with the program provided for download. Prime numbers up to 109 can be download from the page. For prime numbers greater than 1010 some ranges that were generated are presented and available for download.