Sieve of Erastothenes

The algorithm to compute the primes up to N.

Dependencies

1. A C++ compiler compatible with C++20
   1. We use g++ but others should work fine
2. PAPI
3. OpenMP
   1. Only required to compile parallel, spmd and tasks
4. GNU Make
   1. Optional - just for compilation convinience

Usage

make [all | basic | multiples | segmented | parallel | spmd | tasks] # builds a target
./bin/basic.out     # naïve sieve of erastothenes
./bin/multiples.out # fast-marking based sieve of erastothenes
./bin/segmented.out # segmented sieve of erastothenes
./bin/parallel.out  # parallel segmented sieve of erastothenes
./bin/spmd.out      # SPMD segmented sieve of erastothenes
./bin/tasks.out     # parallel sieve using tasks

Authors

• Miguel Rodrigues
• Sérgio Estêvão

CPA @ M.EIC