pythonを使った100以下の素数判定を３種類のやり方で実装してみました。
また、それぞれかかった時間も表示しました。
① print以外の組み込み関数を使わない(timeは除く）
import time
n = 2
t1 = time.time()
while n <= 100:
div = 0
m = 1
while m <= n:
if n % m == 0:
div += 1
m += 1
if div == 2:
print(n)
n += 1
time = time.time() - t1
print("time:{}".format(time))
実行結果
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
0.007971048355102539
② １つずつ確認していく方法
import time
def ma(n):
sosu_list = []
t1 = time.time()
for n in range(2,n + 1):
div = 0
for m in range(1,n + 1):
if n % m == 0:
div = div + 1
if div == 2:
sosu_list.append(n)
print(sosu_list)
t1 = time.time()
ma(100)
time = time.time() - t1
print("time:{}".format(time))
実行結果
[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]
time:0.0027151107788085938
③ エラトステネスの篩
import time
def eratosu(n):
sosu_list = []
false = []
for i in range(2,n+1):
if i not in false:
sosu_list.append(i)
for j in range(i*i,n+1,i):
false.append(j)
return sosu_list
t1 = time.time()
print(eratosu(100))
time = time.time() - t1
print("time:{}".format(time))
実行結果
[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]
time:0.0005650520324707031
①,②はtimeを比較すると基本的にあまり大きく変わりませんでした。ただ、②の方法は時々③に近いスピードが出ていて安定しませんでした。それに比べて③のプログラムはこの中で最も高速であるという結果が得られました。エラトステネスのふるいというアルゴリズムなのですが、とても効率的で計算量が少なかったためでしょう（wikiを参考にしたのでリンクを貼っておきます）
同じ結果を出力するプログラムでも、違う考え方で実装してみるのは考え方が深まって楽しいのでこれからも続けていきたいですね。