Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

はじめに

エラトステネスの篩を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()

結果

sieve_of_eratoshenes_result.png

おまけ

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

pycharm.png


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

# -*- 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))

xxx.png

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした