Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
Get list of prime numbers using Sieve of Eratosthenes. More...
#include <cassert>
#include <iostream>
#include <vector>
Functions | |
std::vector< bool > | sieve (uint32_t N) |
void | print (uint32_t N, const std::vector< bool > &is_prime) |
void | tests () |
int | main () |
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)\)
int main | ( | void | ) |
Main function
void print | ( | uint32_t | N, |
const std::vector< bool > & | is_prime ) |
This function prints out the primes to STDOUT
N | number of primes to check |
is_prime | a vector of N + 1 booleans identifying if i ^th number is a prime or not |
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.
N | number of primes to check |
N + 1
booleans identifying if i
^th number is a prime or not void tests | ( | ) |
Test implementations