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

![EDM5zfOUEAAo6lD.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2100048/32ccc9d0-06a9-1bda-6c9a-254118383347.jpeg)

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

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

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

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

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

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

```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通り考えてみました。

<img src = 'https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2100048/5a63f06f-050b-5048-8d30-dbdc77f03120.jpeg' width = 50%>

**パターン１**
```python
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
```

**パターン２**
```diff_python
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$で止めることで、時を加速させました。

https://cartman0.hatenablog.com/entry/2017/10/23/%E8%87%AA%E7%84%B6%E6%95%B0n%E3%81%8C%E2%88%9An%E4%BB%A5%E4%B8%8B%E3%81%AE%E3%81%99%E3%81%B9%E3%81%A6%E3%81%AE%E7%B4%A0%E6%95%B0%E3%81%A7%E5%89%B2%E3%82%8A%E5%88%87%E3%82%8C%E3%81%AA%E3%81%91%E3%82%8C

パターン２では、更に加速するために、素数だけで判定を行うように改良したつもりでした。
<img src = 'https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2100048/7a1984b3-7f25-042e-bced-49a5817d93d2.png' width = 70%>

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

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

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


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


<img src = 'https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2100048/c35f46ff-46b4-484d-c240-06671cea64c3.jpeg' width = 50%>

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

<details><summary>csvにはきだして比較するためのコード</summary>

```python
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)

```

```diff_python
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)
```

</details>

| | パターン１ 平均 | パターン２ 平均 |　*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}$  |

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


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

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

修正いただいたコードで時を加速させると以下のようになりました。
| | パターン１ 平均 | パターン２ 平均 |　　*p-value　　|
|:-:|:-:|:-:|:-:|
| 100,000  | $0.14 [s]$  | $0.070 [s]$  | $6.36×10^{-201}$  |


優位に**パターン2が早い**という結果となりました。
コードは間違っていましたが、考え方は間違っていなかったようです。
>先日のパターン１ 平均より今回の平均値が大きく改善しているのは、実行しているPCが異なるためです。

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

[エラトステネスの篩](https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9)という誹謗中傷はやめてください（笑）。

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