计算Python中的素数

假设我们有一个极限n。我们必须计算2到n范围内的质数。因此，如果n = 10，则结果将为4。由于在10之前有四个素数，它们分别为2、3、5、7。

为了解决这个问题，我们将遵循这种方法-

• 计数= 0

• 取一个大小为n + 1的素数数组，并用False填充

• 对于i = 0到n

• 计数增加1

• 设j = 2

• 当j * i <n时

• prime [i * j] =真

• j = j + 1

• 如果prime [i] = false，则

• 返回计数

示例

让我们看下面的实现以更好地理解-

class Solution(object):
   def countPrimes(self, n):
      """
      :type n: int
      :rtype: int
      """
      count = 0
      primes = [False for i in range(n+1)]
      for i in range(2,n):
         if primes[i] == False:
            count+=1
            j = 2
            while j*i<n:
               primes[j*i] = True
               j+=1
      return count
ob1 = Solution()
print(ob1.countPrimes(50))
print(ob1.countPrimes(10))

输入值

n = 50
n = 10

输出结果

15
4