primesieve

Fast C/C++ prime number generator

View project onGitHub

About

This page contains a collection of links related to the (segmented) sieve of Eratosthenes. Jonathan Sorenson's papers provide a good introduction to the segmented sieve of Eratosthenes and wheel factorization.

Introductions

  1. Sieve of Eratosthenes
  2. Segmented sieve of Eratosthenes
  3. Wheel factorization
  4. HaskellWiki - Prime numbers, an analysis of many different prime number sieves.

Fast sieve of Eratosthenes implementations

  1. Super Sieve (1988), fast sieve of Eratosthenes prime number finder for 8-bit Atari computers.
  2. The Black Key Sieve (1993), fastest sieve of Eratosthenes program from 1993 to 1998.
  3. The Art of Prime Sieving (1998), Achim Flammenkamp's segmented sieve of Eratosthenes implementation in C.
  4. primegen (1999), D. J. Bernstein's fast sieve of Atkin implementation in C.
  5. Fast implementation of the segmented sieve of Eratosthenes (2002), by Tomás Oliveira e Silva.
  6. ecprime (2002), the author's older segmented sieve of Eratosthenes implementation in C++.
  7. YAFU (2008), by Ben Buhrow, contains a multi-threaded segmented sieve of Eratosthenes written in C.
  8. primesieve (2010), the author's multi-threaded segmented sieve of Eratosthenes implementation in C++.
  9. CUDA Sieve of Eratosthenes (2012), Ben Buhrow's segmented sieve of Eratosthenes implementation for GPUs.
  10. CUDA Sieve of Eratosthenes (2016), Curtis Seizert's sieve of Eratosthenes implementation for GPUs.

Papers about the sieve of Eratosthenes

  1. J. Sorenson, "An Introduction To Prime Number Sieves", January 1990.
  2. J. Sorenson, "An analysis of two prime number sieves", June 1991.
  3. J. Sorenson and I. Parberry, "Two Fast Parallel Prime Number Sieves", 1994.
  4. J. Sorenson, "Trading Time for Space in Prime Number Sieves", 1998.
  5. Jörg Richstein, "Segmentierung und Optimierung von Algorithmen zu Problemen aus der Zahlentheorie", 1999.
  6. P. Sebah and X. Gourdon, "Counting Twin Primes and estimation of Brun's Constant up to 10^16", 2002.
  7. Tomás Oliveira e Silva, "Fast implementation of the segmented sieve of Eratosthenes", 2002.
  8. A. Járai and E. Vatai, "Cache optimized linear sieve", 2011.