お知らせ

ただいま、シンタックスハイライターの設定を見直しております。
プログラムが見にくくなっているページがありますが、ご容赦ください。

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

数学

こんにちは。

2019年も明日で終わりです。

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

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

今回のアルゴリズム

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

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

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

・・・

・・・

・・・

なんと

・・・

・・・

・・・

試し割り法です。

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

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

ちょっとした工夫

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

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

同様に3を除く正の3の倍数,5を除く正の5の倍数は素数ではありません。

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

2・3・5の倍数を除くと,割り算を試す回数が結構減りそうです。

試す必要があるのは,30で割った余りが1・7・11・13・17・19・23・29の数だけです。

これを使うと,試す個数が,およそ30個の数のうち8個だけになります。

全体の1/4程度の数について試せば十分そうです。

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

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

2020年には,25回の素数日があります。

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

Posted by kasugai