Python のエラトステネスのふるい
エラトステネスのふるいは、与えられた数より下の素数を取得するための非常に一般的なアルゴリズムです。この数は 1000 万未満である必要があります。
アルゴリズムは理解しやすく、プログラミングで頻繁に実装されます。このチュートリアルでは、Python のエラトステネスのふるいアルゴリズムの実装について説明します。
まず、このアルゴリズムの背後にあるロジックを理解することから始めましょう。まず、2 の間のすべての数字と提供された数字 50 と仮定しましょうを書きます。
次に、最初の素数 2 を取り、その平方より大きく 2 で割り切れるすべての数をマークします。次に、次の素数 3 で同じことを繰り返します。
素数 77 の後の次の数の二乗が 121 で 50 より大きいまで同じ手順が実行されます。すべての数字をマークした後、マークされていない値は 50 までの素数です。
次の図は、最終結果を示しています。
Python でエラトステネスのふるいを使用する
まず、必要な範囲のリストを作成します。このリストは、指定されたインデックスに対して True または False をマークします。
最初、リストにはすべての要素が True として含まれています。ネストされたループを使用して変更を加え、非プライム位置を False としてマークします。
この後、値がまだ True である位置を新しいリストに保存します。このリストには素数が含まれています。
def sieve_of_eratosthenes(val):
max = val + 1
lst = [True] * max
for i in range(2, int(val ** 0.5 + 1)):
if lst[i]:
for j in range(i * i, max, i):
lst[j] = False
final = []
for i in range(2, max):
if lst[i]:
final.append(i)
return final
print(sieve_of_eratosthenes(100))
出力：
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
時間の複雑さを改善するために、上記のコードに小さな変更を加えることができます。たとえば、セットまたは辞書を使用して、素数以外の数値をフィルタリングできます。
最終結果はリストに返されますが、prime および non-prime 番号を True または False としてマークする際に辞書またはセットを使用してください。
def sieveoferatosthenes_dict(n):
max = n + 1
d = dict()
for i in range(2, max):
d[i] = True
for i in d:
factors = range(i, max, i)
for f in factors[1:]:
d[f] = False
lst = [i for i in d if d[i] == True]
return lst
print(sieveoferatosthenes_dict(100))
出力：
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
上記の例では、辞書 d を使用して値を True または False としてマークし、素数を除外します。最終結果はリストにあります。
Manav is a IT Professional who has a lot of experience as a core developer in many live projects. He is an avid learner who enjoys learning new things and sharing his findings whenever possible.
LinkedIn