<reponame>wanxin-code/leetcode
import math
class Solution: 
    def countPrimes(self, n: int) -> int:
        isPrime = [True]*n
        for i in range(2, n):
            if i*i >= n:   # the upbound of isPrime
                break
            if not isPrime:
                continue
            for j in range(i*i, n, i):  # why begin from i*i? For example:when i==4, (1, 2, 3)*4 has been calculated before. just need begin from 4*4
                isPrime[j] = False
        count = 0
        for x in isPrime[2:]:
            if x:
                count += 1
        return count
import math
class Solution: 
    def countPrimes(self, n: int) -> int:
        isPrime = [True]*n
        for i in range(2, n):
            if i*i >= n:   # the upbound of isPrime
                break
            if not isPrime:
                continue
            for j in range(i*i, n, i):  # why begin from i*i? For example:when i==4, (1, 2, 3)*4 has been calculated before. just need begin from 4*4
                isPrime[j] = False
        count = 0
        for x in isPrime[2:]:
            if x:
                count += 1
        return count
# the upbound of isPrime # why begin from i*i? For example:when i==4, (1, 2, 3)*4 has been calculated before. just need begin from 4*4