Edited at

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()


結果


おまけ

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: コメントで頂いた指摘を反映したコード