在 Python 中生成小于 n 的素数列表

pythonserver side programmingprogramming更新于 2025/12/26 9:16:17

假设我们有一个数字 n，我们必须按升序生成所有小于或等于 n 的素数列表。我们必须记住，1 不是素数。

因此，如果输入为 12，则输出将为 [2, 3, 5, 7, 11]。

为了解决这个问题，我们将遵循以下步骤 −

sieve := 大小为 n+1 的列表并用 True 填充
primes := 一个新列表，最初为空白
对于范围为 2 到 n 的 i，执行
- 如果 sieve[i] 为 True，则
  - 在 primes 的末尾插入 i
  - 对于范围为 i 到 n 的 j，在每个步骤中用 i 更新，执行
    - sieve[j] := False
返回 primes

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

示例

class Solution:
   def solve(self, n):
      sieve = [True] * (n + 1)
      primes = []
      for i in range(2, n + 1):
         if sieve[i]:
            primes.append(i)
            for j in range(i, n + 1, i):
               sieve[j] = False
      return primes
ob = Solution()
print(ob.solve(12))