エラトステネスのふるいのためのPythonプログラム

この記事では、以下に示す問題ステートメントの解決策について学習します。

問題の説明 −数値nが与えられているので、n以下のすべての素数を出力する必要があります。制約：nは小さい数です。

次に、以下の実装のソリューションを見てみましょう-

例

def SieveOfEratosthenes(n):
   # array of type boolean with True values in it
   prime = [True for i in range(n + 1)]
   p = 2
   while (p * p <= n):
      # If it remain unchanged it is prime
      if (prime[p] == True):
         # updating all the multiples
         for i in range(p * 2, n + 1, p):
            prime[i] = False
      p += 1
   prime[0]= False
   prime[1]= False
   # Print
   for p in range(n + 1):
      if prime[p]:
         print (p,end=" ")
# main
if __name__=='__main__':
   n = 33
   print ("The prime numbers smaller than or equal to", n,"is")
   SieveOfEratosthenes(n)

出力

The prime numbers smaller than or equal to 33 is
2 3 5 7 11 13 17 19 23 29 31

すべての変数はローカルスコープで宣言されており、それらの参照は上の図に示されています。

結論

この記事では、エラトステネスのふるい用のPythonプログラムを作成する方法について学びました