Pythonでn未満の素数のリストを生成する

数nがあるとすると、n以下のすべての素数のリストを昇順で生成する必要があります。 1は素数ではないことに注意する必要があります。

したがって、入力が12のような場合、出力は[2、3、5、7、11]になります。

これを解決するには、次の手順に従います-

• ふるい：=サイズn+1のリストとTrueで埋める
• primes：=新しいリスト、最初は空白
• 2からnの範囲のiについては、
  • sieve [i]がTrueの場合、
    • 素数の最後にiを挿入
    • iからnの範囲のjについては、各ステップでiずつ更新します。
      • sieve [j]：=False
• 素数を返す

理解を深めるために、次の実装を見てみましょう-

例

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]