用 Python 计算素数

pythonserver side programmingprogramming更新于 2025/10/31 5:00:17

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

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

count = 0
取一个大小为 n + 1 的数组 prime =，并用 False 填充它
对于 i = 0 到 n，执行
- 如果 prime[i] = false，则
  - 将 count 增加 1
  - 设置 j = 2
  - 当 j * i <n 时，则
    - prime[i * j] = True
    - j = j + 1
返回 count

示例

让我们看下面的实现，以便更好地理解 −

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))