# Accepte, C++ method.

• `````` int countPrimes(int n)
{
if (2 >= n)	return 0;

bool* primes = new bool[n];
for (int i = 2; i < n; ++i)
primes[i] = true;

int sqr = sqrt(n - 1);
for (int i = 2; i <= sqr; ++i)
{
if (primes[i])
{
for (int j = i + i; j < n; j += i)
primes[j] = false;
}
}

int sum = 0;
for (int i = 2; i < n; ++i)
sum += (primes[i]) ? 1 : 0;

delete[] primes;

return sum;
}``````

• for (int j = i + i; j < n; j += i)

should be
for (int j = i * i; j < n; j += i) ?

• it is a great idea!!

• As the wiki said.

``````int countPrimes(int n)
{
if (2 >= n) return 0;

bool* primes = new bool[n];
for (int i = 2; i < n; ++i)
primes[i] = true;

int sqr = sqrt(n - 1);
for (int i = 2; i <= sqr; ++i)
{
if (primes[i])
{
for (int j = i * i; j < n; j += i)
primes[j] = false;
}
}

int sum = 0;
for (int i = 2; i < n; ++i)
sum += (primes[i]) ? 1 : 0;

delete[] primes;

return sum;
}
``````

Not j=i+i It's j=i*i

• you are right!!
thanks

• You could count while iterating through the array. That could save some time:

``````int sum = 0;
for (int i = 2; i < n; ++i)
{
if (primes[i])
{
sum++;
for (int j = i + i; j < n; j += i)
primes[j] = false;
}
}``````

• this will reduce the the amount of code.
But i don't think it will save so many time.

I think, no matter "in" or "out", the two methods will do O(n) "plus operate" .

• From order perspective, it's still O(n). But we could still saving something:
(1) sqr "if (primes[i])" check operations. Originally the two iteration has some duplication.
(2) "sum += (primes[i]) ? 1 : 0;" will have n "plus operation" (either add 1 or 0), while "if (primes[i]) sum++" will have less than n "plus operation" (only add 1).

• yeas you are right

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