Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
sieve_of_eratosthenes.cpp File Reference

Get list of prime numbers using Sieve of Eratosthenes. More...

#include <cassert>
#include <iostream>
#include <vector>
Include dependency graph for sieve_of_eratosthenes.cpp:

Functions

std::vector< bool > sieve (uint32_t N)
 
void print (uint32_t N, const std::vector< bool > &is_prime)
 
void tests ()
 
int main ()
 

Detailed Description

Get list of prime numbers using Sieve of Eratosthenes.

Sieve of Eratosthenes is an algorithm that finds all the primes between 2 and N.

Time Complexity : \(O(N \cdot\log \log N)\)
Space Complexity : \(O(N)\)

See also
primes_up_to_billion.cpp prime_numbers.cpp

Function Documentation

◆ main()

int main ( void  )

Main function

65  {
66  tests();
67 
68  uint32_t N = 100;
70  print(N, is_prime);
71  return 0;
72 }
Here is the call graph for this function:

◆ print()

void print ( uint32_t  N,
const std::vector< bool > &  is_prime 
)

This function prints out the primes to STDOUT

Parameters
Nnumber of primes to check
is_primea vector of N + 1 booleans identifying if i^th number is a prime or not
44  {
45  for (uint32_t i = 2; i <= N; i++) {
46  if (is_prime[i]) {
47  std::cout << i << ' ';
48  }
49  }
51 }
Here is the call graph for this function:

◆ sieve()

std::vector<bool> sieve ( uint32_t  N)

This is the function that finds the primes and eliminates the multiples. Contains a common optimization to start eliminating multiples of a prime p starting from p * p since all of the lower multiples have been already eliminated.

Parameters
Nnumber of primes to check
Returns
is_prime a vector of N + 1 booleans identifying if i^th number is a prime or not
26  {
27  std::vector<bool> is_prime(N + 1, true);
28  is_prime[0] = is_prime[1] = false;
29  for (uint32_t i = 2; i * i <= N; i++) {
30  if (is_prime[i]) {
31  for (uint32_t j = i * i; j <= N; j += i) {
32  is_prime[j] = false;
33  }
34  }
35  }
36  return is_prime;
37 }
Here is the call graph for this function:

◆ tests()

void tests ( )

Test implementations

56  {
57  // 0 1 2 3 4 5 6 7 8 9 10
58  std::vector<bool> ans{false, false, true, true, false, true, false, true, false, false, false};
59  assert(sieve(10) == ans);
60 }
Here is the call graph for this function:
std::vector< bool >
ans
ll ans(ll n)
Definition: matrix_exponentiation.cpp:91
sieve
std::vector< bool > sieve(uint32_t N)
Definition: sieve_of_eratosthenes.cpp:26
is_prime
bool is_prime(T num)
Definition: check_prime.cpp:22
std::cout
print
void print(uint32_t N, const std::vector< bool > &is_prime)
Definition: sieve_of_eratosthenes.cpp:44
std::endl
T endl(T... args)
tests
void tests()
Definition: sieve_of_eratosthenes.cpp:56