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

2019-12-30数学

こんにちは。

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

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

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

1. 今回のアルゴリズム
2. ちょっとした工夫
3. 実行結果

今回のアルゴリズム

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

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

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

・・・

なんと

・・・

試し割り法です。

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

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

ちょっとした工夫

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

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

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

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

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

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

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

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

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

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)

実行結果

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

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

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

Posted by 春日井優