在 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]

Arnab Chakraborty

更新於: 2020-09-23

5 千 + 次瀏覽

啟動你的 職業

透過完成課程來獲得認證

開始