python - 需要帮忙!使用 python 计数素数

Question

计算小于非负数 n 的素数的个数。我创建了以下代码，但复杂度太高。如果有人能给我更好的解决方案，我将不胜感激。

import math
class Solution(object):
    def countPrimes(self, n):
        PrimeCount=0
        primelist=[]
        for i in range(2,n):
            if self.primeCheck1(i,primelist)==True:
                primelist.append(i)       #try2 with new logic
                PrimeCount=PrimeCount+1

        return PrimeCount



    def primeCheck1(self,n,primelist):
        flag=False
        if n==2:
            return True
        elif n==3:
            return True
        sqroot=int(math.sqrt(n))

        for j in range(0,sqroot):
            if n%primelist[j]==0:
                flag=True
                break

        if flag!=True:
            return True
        else:
            return False

Answer 1

我喜欢您构建素数列表并使用该列表检测更大素数的方式。没错，您的代码比需要的复杂得多，特别是不需要您的 flag 变量。

您在 primeCheck1() 方法中也遗漏了一些可以加快速度的技巧。由于我的 Python 不存在，因此这是类似 Python 的伪代码。我假设您将能够转换它。

def primeCheck1(self, n, primelist):

  # Handle even numbers.
  if n % 2 == 0:
        # The only even prime is 2.
        return (n == 2)

  # Handle multiples of 3.
  if n % 3 == 0:
        return (n == 3)

  # Handle remaining numbers.
  sqroot = int(math.sqrt(n))

  for j in range(0, sqroot):
    if n % primelist[j] == 0:
      return False  # Not a prime number.

  # If we get this far then the number is prime.
  return True

end primeCheck1

在一个小问题上，您习惯于不分隔代码:a==b 而不是 a == b。使用空格作为分隔符使代码更易于阅读。