大怪我して孤独なGWを過ごしていたので、同じく孤独な数字 "素数" を数えて時を加速させた話

5月4日（水）
@fujitanozomu さまにご提案いただいた修正内容を追記しております。

靭帯切って何もできない孤独なGW

　普段は春スキーや店舗応援に勤しむGWですが、先日右膝前十字靭帯断裂の怪我を負い、孤独なGWを過ごすこととなりました。

素数は1と自分の数でしか割ることのできない孤独な数字で、私に勇気を与えてくれます。
そこで、少しでもたくさんの素数を数えるために、Pythonでコードを書いてみました。

私は小売業勤務のため、GWの繁忙期は店舗の作業応援に数日入ることがほとんどです。
さすがに靭帯切れた膝で店舗作業は危険なので、今年は免除させていただきました。

素数をPython で数えて落ち着くことにした

import time

def prime_number(a,b):
    prime_list = []
    for i in range(a, b+1): # a ~ bまで繰り返す
        prime = True
        for j in range(2,i): # 2からi-1までで割る
            if i % j == 0:
                prime = False # 割り切れたら素数ではない
                break
        if prime :
            if i == 1: # 1は表示しない
                pass
            else:
                prime_list.append(i) # 素数をリストに追加
    return prime_list

start = 0
end = 0

a = 1
b = 0
while a > b:
    try:
        a = int(input('数字1:'))
        b = int(input('数字2:'))
    except:
        print('数字を入力してください')
    else:
        if a > b:
            print('数字1より数字2が大きくなるように入力してください')
        else:
            start = time.time()
            print(prime_number(a, b))
            end = time.time()
            print(end - start)
            break

コードを実行すると、好きな範囲の素数を教えてくれます。
特別なライブラリ等も使用していないので、3系のPythonであれば問題なく動くはずです。

自分以外の数で全部割っていき、割り切れなかった数が素数という原始的なやり方です。
これではとても時間がかかります。

時を加速させることにした

ですので、時を加速させましょう。
2通り考えてみました。

パターン１

import math
import time

def prime_number(a,b):
    prime_list = []
    for i in range(a, b+1): # a ~ bまで繰り返す
        # print(f'i:{i}')
        prime = True
        for j in range(2, math.floor(math.sqrt(i)) + 1 ): # 2からmath.floor(math.sqrt(i))までで割る
            # print(f'j:{j}')
            if i % j == 0:
                prime = False # 割り切れたら素数ではない
                break
        if prime :
            if i == 1: # 1は表示しない
                pass
            else:
                prime_list.append(i) # 素数をリストに追加
    return prime_list

start = 0
end = 0

a = 1
b = 0
while a > b:
    try:
        a = int(input('数字1:'))
        b = int(input('数字2:'))
    except:
        print('数字を入力してください')
    else:
        if a > b:
            print('数字1より数字2が大きくなるように入力してください')
        else:
            start = time.time()
            print(prime_number(a, b))
            end = time.time()
            print(end - start)
            break

パターン２

import math
import time

def prime_number(a,b):
    prime_list = []
    prime_output = []

    for i in range(2,b+1): # b以下の素数リストを作る
        # print(f'i:{i}')
        # print(f'prime_list:{prime_list}')
        prime = True
+       m = math.sqrt(i)
        for j in prime_list: # 2からmath.floor(math.sqrt(i))までで割る
            # print(f'j:{j}')
-           if j > math.sqrt(b):
+           if j > m:
                break
            elif i % j == 0:
                    prime = False # 割り切れたら素数ではない
                    break
        if prime :
            if i == 1: # 1は表示しない
                pass
            else:
                prime_list.append(i) # 素数をリストに追加
    for i in prime_list :
        if i >= a :
            prime_output.append(i) # a以上の素数をアウトプットするリストに追加
    
    # print(prime_list)
    # print(prime_output)

    return prime_output

start = 0
end = 0

a = 1
b = 0
while a > b:
    try:
        a = int(input('数字1:'))
        b = int(input('数字2:'))
    except:
        print('数字を入力してください')
    else:
        if a > b:
            print('数字1より数字2が大きくなるように入力してください')
        else:
            start = time.time()
            print(prime_number(a, b))
            end = time.time()
            print(end - start)
            break

パターン１は素数判定を$\sqrt n$で止めることで、時を加速させました。

パターン２では、更に加速するために、素数だけで判定を行うように改良したつもりでした。

ですが、パターン２になって更に加速しているように見えませんでした。

問題点は２点ありました。
math.sqrt(i)とするべきところをmath.sqrt(b)と記述
=> 判定している素数の平方根以上は判定しないというコードではなく、入力した数字の平方根以上を判定しないというコードとなっている。

for j in prime_listの中にmath.sqrt(i)が記述されている
=> 変数 j に関するループの中で毎回 i の平方根を計算している。j のループの中で i は変化しないので、ループの外に記述するべき。

2つの世界を100回繰り返して比較した

パターン１と２でそれぞれ10,000までと100,000までの素数を100回数え、かかった時間を比較してみました。
コードは重複が多いので折りたたみに入れています。

csvにはきだして比較するためのコード

import math
import time
import csv

f = open('../data/time_1.csv', 'w')
csvWriter = csv.writer(f)

start = 0
end = 0
prime_list = []

a = int(input('数字1:'))
b = int(input('数字2:'))
rep = int(input('繰り返し回数: '))

csvWriter.writerow([a, b, rep])

for k in range(rep):
    prime_list = []
    list_data = []
    start = time.time()
    for i in range(a, b+1): # a ~ bまで繰り返す
        prime = True
        for j in range(2,math.floor(math.sqrt(i)) + 1): # 2からmath.floor(math.sqrt(i))までで割る
            if i % j == 0:
                prime = False # 割り切れたら素数ではない
                break
        if prime :
            if i == 1: # 1は表示しない
                pass
            else:
                prime_list.append(i) # 素数をリストに追加
    end = time.time()
    spend_time = end - start
    list_data.append(k)
    list_data.append(spend_time)
    csvWriter.writerow(list_data)

csvWriter.writerow(prime_list)

import math
import time
import csv

f = open('../data/time_2.csv', 'w')
csvWriter = csv.writer(f)

start = 0
end = 0

a = int(input('数字1:'))
b = int(input('数字2:'))
rep = int(input('繰り返し回数: '))

csvWriter.writerow([a, b, rep])

for k in range(rep):
    prime_list = []
    prime_output = []
    list_data = []
    start = time.time()
    for i in range(2,b+1): # b以下の素数リストを作る
        # print(f'i:{i}')
        # print(f'prime_list:{prime_list}')
        prime = True
+       m = math.sqrt(i)
        for j in prime_list: # 2からmath.floor(math.sqrt(i))までで割る
            # print(f'j:{j}')
-           if j > math.sqrt(b):
+           if j > m :
                break
            elif i % j == 0:
                    prime = False # 割り切れたら素数ではない
                    break
        if prime :
            if i == 1: # 1は表示しない
                pass
            else:
                prime_list.append(i) # 素数をリストに追加
    for i in prime_list :
        if i >= a :
            prime_output.append(i) # a以上の素数をアウトプットするリストに追加
    end = time.time()
    spend_time = end - start
    list_data.append(k)
    list_data.append(spend_time)
    csvWriter.writerow(list_data)

csvWriter.writerow(prime_output)

	パターン１ 平均	パターン２ 平均	*p-value
10,000	$0.012 [s]$	$0.015 [s]$	$8.17×10^{-13}$
100,000	$0.21 [s]$	$0.26 [s]$	$3.63×10^{-8}$

*p-value は片側・非等分散の t-test に対する値

更に加速させたつもりが有意に遅くなっていたようです。
これでは天国に行けそうにありませんね。

パターン2であれば試行回数が減るため、100,000以下の素数を数える場合は有利になるかと思いましたが、結果はそのようにはなりませんでした。

修正いただいたコードで時を加速させると以下のようになりました。

	パターン１ 平均	パターン２ 平均	*p-value
100,000	$0.14 [s]$	$0.070 [s]$	$6.36×10^{-201}$

優位にパターン2が早いという結果となりました。
コードは間違っていましたが、考え方は間違っていなかったようです。

先日のパターン１ 平均より今回の平均値が大きく改善しているのは、実行しているPCが異なるためです。

これで天国に行けそうです。

エラトステネスの篩という誹謗中傷はやめてください（笑）。

今後の展望

特にありません。
日常生活で素数をかぞえることはないので。