### Definition

An algorithm to find prime numbers up to a number $n$

### Algorithm description

Using a boolean vector of size $n$ iteratively mark all the multiples of nonvisited positions as not primes

### Implementation

Time complexity: $O(tn)$, $t$ is the number of primes between $1$ and $t$

vector<bool> sieve;

void eratothenes_sieve(int n) {
// initialize the list
sieve.resize(n + 1, false);

// multiples of 2 are not primes
for (int i = 4; i <= n; i += 2) {
sieve[j] = true;
}

// multiples of odd numbers
for (int i = 3; i * i <= n; i += 2) {
if (!sieve[i]) {
for (int j = i * i; j <= n; j += 2 * i) {
sieve[j] = true;
}
}
}
}

void is_prime(int n) {
assert(n < sieve.size());
return sieve[n];
}