Pythonで「素数日」を求めたら処理が長すぎて日が暮れそうになった

はじめに

時々Twitter等で「今日は素数日！」のようなツイートをみかけます。
これは、年月日(西暦)を8桁の数に置き換えたときに、それが素数になる日を指します。

例：2019年5月23日　→　20190523(素数)
　　2019年7月19日　→　20190719(素数)

ので、Pythonの練習のため、素数日を求めるコードを書いてみます。

準備

何も考えずにコードを書くと、存在しない日付を表示してしまいます。
考えなければいけないのは以下の項目。

• 月ごとの日数
  • 当然ですが、月ごとに日数が違うので事前に設定しておく必要があります。
  • なので事前に下記のように各月の日数をリスト化しておきましょう。

day = [31,28,31,30,31,30,31,31,30,31,30,31]

• うるう年
  • うるう年のみ2月が29日間になるのでここも考慮に入れる必要があります。
  • うるう年の判定条件は以下の通りです
    • 西暦で示した年が4で割り切れる年はうるう年です
    • 西暦で示した年が100で割り切れる年はうるう年ではありません
    • 西暦で示した年が400で割り切れる年はうるう年です

上記を考慮した、うるう年を判定する関数を事前に定義しておきます。

def Uru(year):
    if year % 4 == 0:
        if year % 100 == 0:
            if year % 400 == 0:
                return 1
            else:
                return 0
        else:
            return 1
    else:
        return 0

返り値が0のときが普通の年、1のときがうるう年。
もっとすっきりと記述する方法あると思いますが、自分の能力ではこれが限界です。
加えて、うるう年のときの日数リストも作っておきます。

day_uru = [31,29,31,30,31,30,31,31,30,31,30,31]

実装したコード

上記準備をもとに下記のコードをとりあえず書きました。

import math
#各部品
year = range(0,10000) #西暦元年から西暦9999年まで調べたい
month = [1,2,3,4,5,6,7,8,9,10,11,12]　#月のリスト
day = [31,28,31,30,31,30,31,31,30,31,30,31]
day_uru = [31,29,31,30,31,30,31,31,30,31,30,31]
prime_day = []　#素数日を格納するリスト

#うるう年判定
def Uru(year):
    if year % 4 == 0:
        if year % 100 == 0:
            if year % 400 == 0:
                return 1
            else:
                return 0
        else:
            return 1
    else:
        return 0

for i in year:
    if Uru(i) == 0:　#うるう年じゃないとき
        for j in month:
            for k in range(1,day[j-1]+1):
                if k % 2 == 0:　#日が偶数の時点で素数にはならないのでここで一度判定
                    continue
                date = i*10000 + j*100 + k　#8桁生成
                date_half = math.ceil(date / 2)
                wari = [l for l in range(3, date_half)]           
                for m in wari[0::2]: #2の倍数を除いた数で対象のdateをひたすら割る 
                    if date % m == 0:
                        break
                    else:
                        if (m == date_half or m == date_half -1):
                            prime_day.append(date)
    else:　#うるう年
        for j in month:
            for k in range(1, day_uru[j-1]+1):
                if k % 2 == 0:
                    continue
                date = i*10000 + j*100 + k
                date_half = math.ceil(date / 2)
                wari = [l for l in range(3, date_half)]          
                for m in wari[0::2]:
                    if date % m == 0:
                        break
                    else:
                        if (m == date_half or m == date_half -1):
                            prime_day.append(date)

print(prime_day)

これで一度実行したんですが、CPUファンの回転数が「ファーン↑↑」と上がったっきり結果が帰ってきませんでした。
冷静に考えればわかることですが、9999年分判定すると9999*365=3,649,635 日分を判定することになります。
日が偶数の日は処理がすぐ終わる(と思う)ので、実際にはその半分。
それでも、更にそこから素数かどうかの判定が都度入るので、PCの計算が追いつかないんですね。。。
こればっかりは、効率的な素数判定のアルゴリズムを勉強しないとどうにもならないので、
諦めて指定した年の素数日判定するコードにしたいと思います。

import math

year = input("input year:")　#調べたい年を1つ入力
month = [1,2,3,4,5,6,7,8,9,10,11,12]
day = [31,28,31,30,31,30,31,31,30,31,30,31]
day_uru = [31,29,31,30,31,30,31,31,30,31,30,31]
prime_day = []

def Uru(year):
    if year % 4 == 0:
        if year % 100 == 0:
            if year % 400 == 0:
                return 1
            else:
                return 0
        else:
            return 1
    else:
        return 0

i = int(year)
if Uru(i) == 0:
    for j in month:
        for k in range(1,day[j-1]+1):
            if k % 2 == 0:
                continue
            date = i*10000 + j*100 + k
            date_half = math.ceil(date / 2)
            wari = [l for l in range(3, date_half)]          
            for m in wari[0::2]:
                if date % m == 0:
                    break
                else:
                    if (m == date_half or m == date_half -1):
                        prime_day.append(date)
else:
    for j in month:
        for k in range(1, day_uru[j-1]+1):
            if k % 2 == 0:
                continue
            date = i*10000 + j*100 + k
            date_half = math.ceil(date / 2)
            wari = [l for l in range(3, date_half)]          
            for m in wari[0::2]:
                if date % m == 0:
                    break
                else:
                    if (m == date_half or m == date_half -1):
                        prime_day.append(date)

print(prime_day)

試しに2019年でコードを動かしてみます。
これでも結果が返ってくるのに1分かかりました。

[20190221, 20190227, 20190301, 20190319, 20190323, 20190421, 20190523, 20190529, 20190601, 20190613, 20190719, 20190811, 20190823, 20190913, 20191009, 20191027, 20191109, 20191117, 20191231]

というわけで、今年は素数日が19日あるみたいです。

最後に

大晦日が素数日ってなんかエモいやん？