Qiita Teams that are logged in
You are not logged in to any team

Community
Service
Qiita JobsQiita ZineQiita Blog
20
Help us understand the problem. What is going on with this article?
@fantm21

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

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

20
Help us understand the problem. What is going on with this article?
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