需要帮助！使用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

首先用pip install sympy安装sympy包。那么试试这个：

import sympy
PrimeCount=0
n=int(input("Number?"))
for elem in range(n):
   if sympy.isPrime(elem):
      PrimeCount+=1
print(PrimeCount)

Answer 2

我喜欢你建立一个素数列表并用这个列表来检测更大的素数。你说得对，你的代码比它需要的复杂，特别是你的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而不是{}。使用空格作为分隔符使代码更易于阅读。在

Answer 3

重新编写代码，将少于100万的素数计算在内，速度提高3倍：

class Solution(object):
    def countPrimes(self, n):
        primelist = []

        for i in range(2, n):
            if self.primeCheck(i, primelist):
                primelist.append(i)

        return len(primelist)

    def primeCheck(self, n, primes):

        if n < 2:
            return False

        if n % 2 == 0:  # 2 is the only even prime
            return n == 2

        for prime in primes:

            if prime * prime > n:  # easier to square many than sqroot one
                return True

            if n % prime == 0:  # divisible by a prime, not a prime
                return False

        return True

solution = Solution()

print(solution.countPrimes(1000000))

这包括@rossum向你指出的一些技巧。在

但是，我们可以做得更好。下面是一个使用@ClockSlave's prime sieve code的重新实现，当计算小于100万的素数时，它比原来快了22倍：

^{2}$

这里的胜利是消除所有这些昂贵的分歧。在