Prime Numbers

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;
        }
    }
}