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

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

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

为了解决这个问题，我们将按照以下步骤进行操作 −

  • sieve := 大小为 n+1 的列表并用 True 填充
  • primes := 一个新的列表，最初为空
  • 在 2 到 n 的范围内，对于 i，执行
    • 如果 sieve[i] 为 True，则
      • 将 i 插入到 primes 的末尾
      • 对于在每一步中更新范围 i 到 n 的 j，执行
        • 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))

输入

12

输出

[2, 3, 5, 7, 11]

更新于: 2020-09-23

5 千 + 次浏览

启动你的 职业

通过完成课程来获得认证

开始
广告