有关python埃筛法解决问题依旧超时

Question

class Solution:#求小于n的质数个数
    def countPrimes(self, n: int) -> int:
        if n<=2:
            return 0
        elif n==3:
            return 1
        else:
            k=''
            a=[1]*n#忽略a[0],且1不算素数，答案-2
            for i in range(2,int((n-1)**0.5)+2):
                s=i
                tmp=2
                while s<=n-1:
                    s=i*tmp
                    if s<=len(a)-1:
                        a[s]=0
                        tmp+=1
            return a.count(1)-2#答案-2

请问怎么改进才能不超时！QAQ

Answer 1

import time

# 1.1埃氏筛，速度更快
class Solution:#求小于n的质数个数
    def countPrimes(self, n: int) -> int:
        if n<=2:
            return 0
        elif n==3:
            return 1
        else:
            a=[1]*n#忽略a[0],且1不算素数，答案-2
            ll = len(a) - 1
            for i in range(2,int((n-1)**0.5)+2):
                s=i
                tmp=2
                if a[s] == 1:                    
                    while s<=ll:
                        s=i*tmp
                        if s<=ll : a[s]=0
                        tmp+=1
            return a.count(1)-2#答案-2
 
s =time.time()       
a = Solution()
r = a.countPrimes(5000000)
print(r)
print(time.time() - s)