204. Count Primes

class Solution:
    def countPrimes(self, n: int) -> int:
        if n<=2:return 0
        a=[True]*(n)
        a[0]=a[1]=False
        a[2]=True
        i=2
        while i**2<n:
            if a[i]:
                for j in range(i**2,n,i):
                    a[j]=False
            i+=1

        return a.count(True)


class Solution:
    def countPrimes(self, n: int) -> int:
        if n<=2:return 0
        a=[True]*(n)
        a[0]=a[1]=False
        a[2]=True
        for i in range(2,int(n**0.5)+1):
            if a[i]:
                j=i**2
                while j<n:
                    if j%i==0:a[j]=False
                    j=j+i

        return a.count(True)