class Solution: """ @param n: a integer @return: return a integer """ def countPrimes(self, n): # write your code here prime =  * n prime = prime = 0 for each in range(2,int(n**0.5)+1): if prime[each]: prime[each*each: n: each] =  * len(prime[each*each:n:each]) return sum(prime)
First, we assume all numbers from 0 to N are prime, so as True.
Then, set number 0 and 1 to false, because they are not prime
from 2 to int(n**0.5) +1 is for calculation improvement, to reducing those number that after.
You can do 2 to n if you want, but there is no point to do that.
Example: n = 25, because they're the results of each*each all be all above 25 after we check number 5.
Why we check the prime [each*each] instead of their multiplier? For example, N =25.
Becuase for prime [each*2] we already marked as none prime when each = 2, same as 3, 4 each
prime[each*each: n: each] =  * len(prime[each*each:n:each])
will set all numbers of square of number, and increamental of itself to False.
Calculate the sum of prime, which is all true prime.