Links

This page contains a collection of links related to the segmented sieve of Eratosthenes. These links are a useful resource for programmers who are trying to optimize their own sieve of Eratosthenes implementation because this requires in depth knowledge of the algorithms and other fast open source prime sieve implementations.

General links

• Segmented sieve of Eratosthenes, by Kim Walisch
• Segmented sieve, by GeeksForGeeks
• Prime Sieve Benchmarks, by Dana Jacobsen
• Wikipedia: Sieve of Eratosthenes
• Wikipedia: Wheel factorization
• HaskellWiki: Prime numbers, an analysis of many different prime number sieves.

Fast sieve of Eratosthenes implementations

• Super Sieve (1988),
  fast sieve of Eratosthenes prime number finder for 8-bit Atari computers.
• The Black Key Sieve (1993),
  fastest sieve of Eratosthenes program from 1993 to 1998.
• The Art of Prime Sieving (1998),
  Achim Flammenkamp's segmented sieve of Eratosthenes implementation in C.
• primegen (1999),
  D. J. Bernstein's fast sieve of Atkin implementation in C.
• Fast implementation of the segmented sieve of Eratosthenes (2002),
  by Tomás Oliveira e Silva.
• ecprime (2002),
  the author's older segmented sieve of Eratosthenes implementation in C++.
• YAFU (2008),
  by Ben Buhrow, contains a multi-threaded segmented sieve of Eratosthenes written in C.
• primesieve (2010),
  the author's multi-threaded segmented sieve of Eratosthenes implementation in C++.
• ktprime (2012),
  by Huang YuanBing, fastest open source prime k-tuplet sieve in C/C++.
• Math-Prime-Util (2012),
  by Dana Jacobsen, Perl number theory library with optimized C sieve.
• hprime (2015),
  by Tristan Verniquet, highly optimized C code, extremely fast ≤ 10^9.
• CUDA Sieve of Eratosthenes (2012),
  Ben Buhrow's segmented sieve of Eratosthenes implementation for GPUs.
• CUDA Sieve of Eratosthenes (2016),
  Curtis Seizert's sieve of Eratosthenes implementation for GPUs.

Papers about the sieve of Eratosthenes

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