LeetCode - 求小于n的素数的个数

没有提交成功，超时了。性能不行。

class Solution:
    def getPrimes(self, n: int) -> list:
        if n in [0, 1, 2]:
            return []
        elif n in [3]:
            return [2]
        elif n in [4, 5]:
            return [2, 3]
        elif n in [6, 7]:
            return [2, 3, 5]
        elif n in [8, 9, 10]:
            return [2, 3, 5, 7]
        elif n <= 100:
            return [2, 3, 5, 7] + [j for j in range(11, n, 2) if j % 3 != 0 and j % 5 != 0 and j % 7 != 0]
        elif n <= 10000:
            srt = int(n ** 0.5)
            srt = srt if srt % 2 == 0 else srt + 1
            primes_srt = self.getPrimes(srt)
            primes = []
            i = srt + 1
            while i < n:
                is_prime = True
                for p in primes_srt[1:]:
                    if i % p == 0:
                        is_prime = False
                        break
                if is_prime:
                    primes.append(i)
                i += 2
            return primes_srt + primes
        else:
            raise ValueError('n must be less than or equal to 10000!')


    def countPrimes(self, n: int) -> int:
        if n in [0, 1, 2]:
            return 0
        elif n <= 10000:
            return len(self.getPrimes(n))
        elif n <= 100000000:
            srt = int(n ** 0.5)
            srt = srt if srt % 2 == 0 else srt + 1
            primes_srt = self.getPrimes(srt)
            cnt = 0
            i = srt + 1
            while i < n:
                is_prime = True
                for p in primes_srt[1:]:
                    if i % p == 0:
                        is_prime = False
                        break
                if is_prime:
                    cnt += 1
                i += 2
            return len(primes_srt) + cnt
        else:
            raise ValueError('n must be less than or equal to 100000000!')