# From 700ms to 300ms to 200ms to 100ms to 28ms to 16ms

• 700ms - most direct and intuitive solution

class Solution {
public:
int countPrimes(int n) {
if(!n || n==1) return 0;
vector<bool> numbers(n, true);
numbers[0] = numbers[1] = false;
for(int i = 2; i <= sqrt(n); i++)
for(int j = i*i; j < n; j += i)
if(numbers[j]) numbers[j] = false;
int count = 0;
for(auto i: numbers)
if(i) count++;
return count;
}
};

300ms - if it's checked then just skip

class Solution {
public:
int countPrimes(int n) {
if(!n || n==1) return 0;
vector<bool> numbers(n, true);
numbers[0] = numbers[1] = false;
for(int i = 2; i <= sqrt(n); i++)
if(numbers[i])
for(int j = i*i; j < n; j += i)
numbers[j] = false;
int count = 0;
for(int i = 0; i < n; ++i)
if(numbers[i]) count++;
return count;
}
};

200ms - actually half of the numbers can just be ignored since they can divided by 2;

class Solution {
public:
int countPrimes(int n) {
if(n < 3) return 0;
vector<bool> numbers(n, true);
numbers[0] = numbers[1] = false;
for(int i = 3; i <= sqrt(n); i += 2)
if(numbers[i])
for(int j = i*i; j < n; j += i)
numbers[j] = false;
int count = 1;
for(int i = 3; i < n; i += 2)
if(numbers[i]) count++;
return count;
}
};

100ms - using array to replace vector and meantime move twice quicker than before since we've removed even numbers.

class Solution {
public:
int countPrimes(int n) {
if(n < 3) return 0;
bool *numbers = new bool[n];
memset(numbers, 1, sizeof(bool)*n);
numbers[0] = numbers[1] = false;
for(int i = 3; i <= sqrt(n); i += 2)
if(numbers[i])
for(int j = i*i, k = i<<1; j < n; j += k)
numbers[j] = false;
int count = 1;
for(int i = 3; i < n; i += 2)
if(numbers[i]) count++;
return count;
}
};

16ms - merge these two loops

class Solution {
public:
int countPrimes(int n)
{
if(n < 3) return 0;
bool *numbers = new bool[n];
memset(numbers, 1, sizeof(bool)*n);
int count = n/2;
for(int i = 3; i <= sqrt(n); i += 2)
if(numbers[i])
for(int j = i*i, k = i<<1; j < n; j += k)
{
if(numbers[j]) count--;
numbers[j] = false;
}
return count;
}
};

This is the best I can do, if you have better solutions please comment below! Thanks!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.