2020年の素数日を調べてみた

数学

こんにちは。

２０１９年も明日で終わりです。

今年はなんとか月に１０回ずつサイト更新をすることができました。来年もがんばります。

昨年の最終回に取り上げた素数日の記事が，案外PVが多かったので，今年も取り上げることにします。

今回のアルゴリズム

昨年は，エラトステネスの篩で調べました。

しかし，高々３６６個の整数が素数か否か調べるには，無駄が多いような気がします。

そこで，今回採用するアルゴリズムは・・・

・・・

・・・

・・・

なんと

・・・

・・・

・・・

試し割り法です。

約数の候補になりうるすべての数で割ってみて，割り切れなければ素数というものです！

ちょ～～～～～～ぉっ素朴なアルゴリズムです。

ちょっとした工夫

しかし，少しだけ工夫します。

２を除く正の偶数は素数ではありません。

同様に３を除く正の３の倍数，５を除く正の５の倍数は素数ではありません。

素数でないことがわかっている数を，繰り返し試しても仕方ありません。

２・３・５の倍数を除くと，割り算を試す回数が結構減りそうです。

試す必要があるのは，３０で割った余りが１・７・１１・１３・１７・１９・２３・２９の数だけです。

これを使うと，試す個数が，およそ３０個の数のうち８個だけになります。

全体の１／４程度の数について試せば十分そうです。

これをプログラムにしてみます。

count = 0
year = 2020
days = [ 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 ]
for m, ds in enumerate( days ):
	for d in range( 0, ds, 2 ):
		i = year * 10000 + (m+1) * 100 + d + 1
		j = 0
		flag = not ( ( i % 3 ) == 0 or ( i % 5 ) == 0 )
		while flag and ( j * j * 900 < i ):
			if j > 0 and ( i % (j*30+1) ) == 0:
				flag = False
				break
			if ( i % (j*30+7) ) == 0:
				flag = False
				break
			if ( i % (j*30+11) ) == 0:
				flag = False
				break
			if ( i % (j*30+13) ) == 0:
				flag = False
				break
			if ( i % (j*30+17) ) == 0:
				flag = False
				break
			if ( i % (j*30+19) ) == 0:
				flag = False
				break
			if ( i % (j*30+23) ) == 0:
				flag = False
				break
			if ( i % (j*30+29) ) == 0:
				flag = False
				break
			j += 1
		if flag:
			print(i)
			count += 1
		i += 2
print(count)

実行結果

それでは，実行結果です。

20200109
20200111
20200121
20200123
20200223
20200309
20200429
20200511
20200529
20200613
20200619
20200703
20200711
20200721
20200723
20200729
20200801
20200813
20200903
20201021
20201029
20201101
20201113
20201227
20201231
25

２０２０年には，２５回の素数日があります。

ということで今年はこれでおしまいにします。よいお年をお迎えください。

Posted by 春日井 優