Parallel Sieve of Eratosthenes / OpenMP
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.
LICENSE set up GitHub mirror Aug 9, 2018
prime.cpp zlib style license Apr 24, 2013 set up GitHub mirror Aug 9, 2018

This is a mirror of my library hosted at

Parallel Sieve of Eratosthenes

There are 50,847,534 prime numbers between 2 and 1,000,000,000. For reasons unknown, I wanted to know whether a C++ implementation can find all these numbers on my modest desktop computer (Intel Core i7 860, quad-core, hyperthreading, 2.8GHz) in less than 1 second with a simple algorithm such as the Sieve of Eratosthenes.

By only slightly modifying the basic algorithm and unleashing the raw power of OpenMP, I achieved a 20x speed-up.

More ...

See my website for code examples and benchmarks. You'll find the Sieve in PHP and Javascript/Asm.js, too (but not parallelized, though).