*LeetCode 204 – Python 3 (Week 06 – 04)

 class Solution:
    def countPrimes(self, n: int) -> int:
        
        if n < 3: return 0
        
        s = [1] * n
        s[0] = 0
        s[1] = 0
        
        #first one is i*i, thus when i*i > n will do nothing.
        for i in range(2,int(n ** 0.5) + 1): 
            if s[i] == 1:
                #As (i-1)*i is already marked in the previous case of i-1, so we can start from i*i
                s[i*i:n:i] = [0] * len(s[i * i:n:i])
            
        return sum(s)
    
    

    
       #O[n*(1+1/2+1/3+1/4+1/5+1/6+…1/int(n ** 0.5) + 1))]