Pythonで作るエラトステネスのふるい

本記事は、コメントで指摘されていますが、「エラトステネスの篩」ではなく「試し割り法」とのことです。
また、下記記事で指摘されているのですが、「エラトステネスの篩」として、「試し割り法」と「似非エラトステネスの篩」が多く見受けられるとのことです。誤った情報を発信しており、申し訳ありません。

本当は遅い「似非エラトステネスの篩」の罠
https://zenn.dev/noodlewhale/articles/c5b069237ee72a

はじめに

エラトステネスの篩をPythonで書いたよって話。

以前作ったコード

Pythonで書く『エラトステネスのふるい』

# -*- coding:utf-8 -*-


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data


def main():
    data = get_sieve_of_eratosthenes(100)
    print(' '.join(map(str, data)))
    print("2～{0}までで以上が素数です\n".format(100))


if __name__ == '__main__':
    main()

実行結果

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
2～100までで以上が素数です

今回作ったコード

# -*- coding:utf-8 -*-
import math


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


if __name__ == '__main__':
    data = get_sieve_of_eratosthenes(100)
    print(' '.join(map(str, data)))
    print("2～{0}までで以上が素数です\n".format(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
2～100までで以上が素数です

---

比較

ソースコード

# -*- coding:utf-8 -*-
import time


def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


def get_sieve_of_eratosthenes_old(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data


def main():
    n = 5000
    s_time = time.time()
    get_sieve_of_eratosthenes_new(n)
    print("New: ", time.time() - s_time)
    s_time = time.time()
    get_sieve_of_eratosthenes_old(n)
    print("Old: ", time.time() - s_time)


if __name__ == '__main__':
    main()

比較結果

New:  0.0027730464935302734
Old:  0.32886290550231934

グラフで比較

ソースコード

# -*- coding:utf-8 -*-
import time
import numpy as np
import matplotlib.pyplot as plt


def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


def get_sieve_of_eratosthenes_old(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data


def main():
    new_time = []
    old_time = []
    count = []
    for i in range(1, 100):
        n = (i + 1) * 10
        s_time = time.time()
        get_sieve_of_eratosthenes_new(n)
        new_time.append(time.time() - s_time)
        s_time = time.time()
        get_sieve_of_eratosthenes_old(n)
        old_time.append(time.time() - s_time)
        count.append(n)
    plt.subplot(111)
    plt.plot(np.array(count), np.array(new_time), label="new")
    plt.plot(np.array(count), np.array(old_time), label="old")
    leg = plt.legend(loc='best', ncol=2, mode="expand", shadow=True, fancybox=True)
    leg.get_frame().set_alpha(0.5)
    plt.show()


if __name__ == '__main__':
    main()

結果

おまけ

PyCharm使うとこんな感じに開発できるのでいいぞ♪
個人であれば商用で使用する場合でも無料版を使えます。（自分は有料版使ってるけど。）
ただ、会社で使用する場合は購入する必要があるので注意。

---

コメントの内容を反映して改善して頂いたコード

# -*- coding:utf-8 -*-


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


if __name__ == '__main__':
    data = get_sieve_of_eratosthenes(100)
    print(' '.join(map(str, data)))
    print("2～{0}までで以上が素数です\n".format(100))

ver1: ブログで書いたコード
ver2: 本記事を書いた時に書いたコード
ver3: コメントで頂いた指摘を反映したコード