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

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

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

# はじめに
[エラトステネスの篩](https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9)をPythonで書いたよって話。

# 以前作ったコード
[Pythonで書く『エラトステネスのふるい』](https://fumisite.net/2018/05/02/python%E3%81%A7%E6%9B%B8%E3%81%8F%E3%80%8E%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E3%81%B5%E3%82%8B%E3%81%84%E3%80%8F/)

```python3:
# -*- 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()

```

# 実行結果

```terminal:
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までで以上が素数です
```


# 今回作ったコード

```python:
# -*- 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))

```

# 実行結果

```terminal:
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までで以上が素数です
```

---

# 比較

## ソースコード

```python:
# -*- 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()

```

## 比較結果

```terminal:
New:  0.0027730464935302734
Old:  0.32886290550231934
```

# グラフで比較

## ソースコード

```python:
# -*- 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()
```

## 結果

![sieve_of_eratoshenes_result.png](https://qiita-image-store.s3.amazonaws.com/0/32946/ba5a0ff0-0510-e823-273e-db3582fd1592.png)

# おまけ

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

<img width="1792" alt="pycharm.png" src="https://qiita-image-store.s3.amazonaws.com/0/32946/50a34f0c-89e2-e7dc-4c44-f7bbccd022a6.png">

---

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

```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')
    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))

```

<img width="1792" alt="xxx.png" src="https://qiita-image-store.s3.amazonaws.com/0/32946/b66e5bad-0422-124e-dc77-8d34dc9f42da.png">

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