チートな素数日判定

素数日判定という遊びがあることを知ったので，チートな方法を考えてみた．

MINYEAR=1，MAXYEAR=9999というPythonの仕様上，

- startが1/1/1 -> 10101
- endが9999/12/31 -> 99991231

なので，予めこの範囲の素数リストを作って辞書としてもち，キー判定することを考える．Unixコマンドのprimesを使う．このコマンドは，aptが使える場合は以下でインストールできる．

```shell-session
sudo apt install bsdgames
```

素数リストを生成する．

```shell-session
$ time primes 10101 99991232 > primes.txt

real    0m1.107s
user    0m0.500s
sys     0m0.594s
```

これで必要な範囲の素数リストができたので，以下のように1/1/1から9999/12/31 までの素数日をリストする．
1/1/1から9999/12/31までのdatetime.dateを生成し，8桁フォーマットにした数がprimesにあるかどうかを調べる．

```python:primedays.py
from datetime import date

with open('primes.txt','r') as f:
    plines = f.readlines()
    primes = { int(x): True for x in plines }

dayrange = range(date(1,1,1).toordinal(),date(9999,12,31).toordinal()+1)
days = [ date.fromordinal(x) for x in dayrange ]

primedays = list(filter(lambda day: int(day.strftime('%Y%m%d')) in primes.keys(), days ))

for day in primedays:
    print(day)
```

1/1/1から9999/12/31までの素数日の個数をカウントしてみる(本来，len(primedays)でよいけれど ;-)．

```shell-session
$ time python3 primedays.py | wc -l
216490

real    0m12.155s
user    0m11.313s
sys     0m1.484s
```

216490日あることがわかる．12秒ちょいとそこそこ速い．素数リストをprimesで生成する作業は1秒くらいでできているので，毎回リスト生成したとしても15秒前後(この後の2019年分の実行結果参照)というところか．

ちなみに最初に書いたときに思い付きで`dict`にしたけれど，hashableなものであれば`tuple`でも`set`でも大体同じような演算時間で(その場合は`day in primes`にする)，`list`にするとかなり遅くなる．

素数の一覧を予め持っておいて判定するというところが，最初に書いた通りチートなわけだが，リストとしてもてるサイズの問題であれば，簡便に速度を出せる常套手段ということで．

2019年の素数日を求めるために，dayrangeを，

```python
dayrange = range(date(2019,1,1).toordinal(),date(2019,12,31).toordinal()+1)
```
と変更して実行してみる．

```shell-session
$ time python3 primedays.py 
2019-02-21
2019-02-27
2019-03-01
2019-03-19
2019-03-23
2019-04-21
2019-05-23
2019-05-29
2019-06-01
2019-06-13
2019-07-19
2019-08-11
2019-08-23
2019-09-13
2019-10-09
2019-10-27
2019-11-09
2019-11-17
2019-12-31

real	0m4.159s
user	0m2.344s
sys		0m1.734s
$
```
この結果をみる限り，最初の素数リスト読込にかかっている時間が結構長そうですね．

実際，ある特定の1年の素数日を求めるだけであれば，sympyモジュールのfactorint() を使う方が速くできます．桁数が8桁なので素因数分解も実用的な速度．
`factorint(int,multiple=True)` とmultipleオプションをTrueにしてあげると素因数をリストで返してくれるので，その長さが1であれば素数ですよね，って，これも不精してるという意味ではそれなりにチートか．

```python:primefactor.py
from datetime import date
from sympy import factorint as ifac

dayrange = range(date(2019,1,1).toordinal(),date(2019,12,31).toordinal()+1)
days = [ date.fromordinal(x) for x in dayrange ]
primedays = list(filter( lambda day: len(ifac(int(day.strftime('%Y%m%d')),multiple=True)) == 1, days ))

for day in primedays:
    print(day)
```

このprimefactor.pyで2019年の素数日を求めると，0.6秒ほど．もちろん，9999年分を求めると逆にprimefactor.pyの方が遅くなって，5分10秒ほど．普通にやる分にはfactorint()で十分かな．素数リストを`sympy.primerange(10101,99991232)`で生成するのもやってみたけど，こちらは遅すぎて使えなかった．

もっとも，単にある日が素数日かどうかを判定するだけであればシェルスクリプトで十分で，以下のように書ける(スケルトンということで入力データのチェックは省略)．

```shell:isprimeday.sh
echo -n 'date(yyyymmdd)> '
read d

p=x`primes ${d} $((d+1))`

if [ ${p} != 'x' ]; then
    echo ${d} is a prime day.
else
    echo ${d} is not a prime day.
fi
```

試してみる．

```shell-session
$ bash isprimeday.sh
date(yyyymmdd)> 20190719
20190719 is a prime day.
$ bash isprimeday.sh
date(yyyymmdd)> 20190720
20190720 is not a prime day.
$
```
primesコマンドが手軽に入らないシステムでは，システム標準のfactorコマンドを使う手もあり．こちらは，`factor 127`の結果が`127: 127`のように返ってくるので，結果の単語数が2なら素数，という流れ．

```sh:factor.sh
echo -n 'date(xxxxmmdd)> '
read d 

f=`factor ${d} | wc -w`

if [ ${f} = 2 ]; then
    echo ${d} is a prime day.
else
    echo ${d} is not a prime day.
fi
```