204.Count Primes計算n以内素数の個数Python

非負数nより小さい質量数を計算する.
Input: 10
Output: 4(2,3,5,7)
素数は1とそれ自体を除いて他の数では割り切れない数です
最初は素数ごとに素数かどうかを判断して取り除く方法を使っていましたが実行がタイムアウトしました><

class Solution:
    def countPrimes(self, n: int) -> int:
        res=list(range(2,n)) #  2 n list
        for i in range(2,n+1): #     n,   n+1
            for j in range(2,int(i**0.5)+1): #  i           ,     list   
                if i%j==0 and i in res:
                 res.remove(i)               
        return len(res)

最適化すると、最初の2つの数を除いてすべて1のリストになり、素数でなければ0になります

class Solution:
    def countPrimes(self, n: int) -> int:
        res=[0,0]+[1]*(n-2)
        for i in range(2,int(n**0.5)+1):
            for j in range(2*i,n,i): #i 2   ,2i,2i+i,2i+2i,2i+3i...n
                res[j]=0
        return sum(res) #res      

 1. n開方後の数は前の素数の倍数なのでn*0.5
2.listを作成して直接累積を設定するのではなく、2つのforループが中の数を繰り返し計算するので、例えばn=10で、ループの中の6は2と3で除去できるので、6に対して2回操作しました.
素数とそのアルゴリズムについてはhttps://en.wikipedia.org/wiki/Sieve_of_Eratosthenes中には直感的な図があります