计算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