## Prime Numbers in [1, n]

The naive method takes O(n^1.5)) time.

```
// O(sqrt(a))
bool IsPrime(a) {
if (a < 2) return false;
for (int i = 2; i * i <= a; ++i) {
if (a % i == 0) {
return false;
}
}
return true;
}
vector<int> primes;
// use long long to avoid that i*i overflows
for (long long i = 2; i <= n; ++i) {
if (IsPrime[i]) {
primes.push_back(i);
}
}
```

We could use the famous Sieve of Eratosthenes algorithm.

```
vector<int> primes;
vector<bool> is_prime(n, true);
// O(nloglogn)
// https://oi-wiki.org/math/sieve/
// use long long to avoid that i*i overflows
for (long long i = 2; i <= n; ++i) {
if (is_prime[i]) {
primes.push_back(i);
for (long long j = i * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
```