An algorithm to find all prime numbers from 1 to n, with O(n) time complexity.
Brute force solution costs O(sqrt(n)) for each number from 1 to n.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int countPrimes(int n) {
vector<bool> tmp(max(2, n), true);
tmp[0] = tmp[1] = false;
int t = sqrt(n);
for (int i = 2; i <= t; ++i) {
if (tmp[i]) {
for (int x = i * i; x < n; x += i) {
tmp[x] = false;
}
}
}
int count = 0;
for (int i = 0; i < n; ++i)
count += tmp[i];
return count;
}