エラトステネスの篩で素数列挙【Python】 - ebisukeプログラミング初心者脱出黙示録

ある値以下の素数を列挙する方法のひとつにエラトステネスの篩（ふるい）があります。

この記事ではPythonでエラトステネスの篩をプログラミングしていきます。

エラトステネスの篩とは

次のように整数n以下の素数を高速にすべて列挙する方法です。

まず2からnまでの数を考え、この数字のなかで最も小さい数字をpとおき、n以下かつp以外のpの倍数をすべて消していきます。

消し終えたら、その中で最も小さい数字をpとおき倍数を消していく・・・という作業を繰り返します。

pが√nを超えたら終了です。

このときに残った数字が素数になります。

素数列挙プログラム(n = 100の場合)

# x以下の素数列挙
def sieve_of_eratosthenes(x):
    nums = [i for i in range(x+1)]

    root = int(pow(x,0.5))
    for i in range(2,root + 1):
        if nums[i] != 0:
            for j in range(i, x+1):
                if i*j >= x+1:
                    break
                nums[i*j] = 0

    primes = sorted(list(set(nums)))[2:]

    return primes


p = sieve_of_eratosthenes(100)

print(p)
# --> [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]
print(len(p))
# --> 25