python で指定した範囲内で素数を数えるプログラムのコードスニペットです。

落ちつくために素数を数えたいとき、はたして脳内で計算した素数はあっているのか。気になって夜も眠れませんね（？）

当ページではちょっとしたパズル問題(CTF)を解くときに書いたコードを整形したものです。

関数の形で再利用可能な形で書いてるので、必要でしたらご自由に改変してお使いください。

python の Numpy などのライブラリは非使用です。

動作確認済み環境

• python 2.7.15、3.8.5

コード

get_primelist(upper) は 2 ～ upper までの素数を数える関数です。

素数だけを配列に格納して返してくれます。

def get_primelist(upper):
	result = []
	for cp in range ( 2, upper + 1 ):
		for i in range ( 2, cp ):
			if ( cp % i == 0 ):
				break
		else:
			result.append(cp)
	return result

# RUN
# 結果で 以下の 100 までの素数が配列で得られる
# [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
#  43,47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ]
print (get_primelist(100))

速度を求めないで良い場合、非常にシンプルなアルゴリズムで記載した上のプログラムでも 2～100,000 の範囲くらいはすぐに計算できるので、頑張ってチューニングしなくても良さそうです。

ご参考・処理時間等

以下、実用的な範囲の計算目安です。

Linux 上で time コマンドで実行し結果表示まで含めた時間です。

計測した環境

• Python : python3.8.2
• OS : Ubuntu 20.04 LTE @ Windows10 Home x64 WSL2
• Processor : Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz
• RAM : 8.00GB

ちゃんと数学ライブラリとか使えばもっと完結で素早い 素数が得られると思うので、そのあたりは追記するかも。

高速化メモ

エラトステネスの篩をかけるようにして、枝を切るようにする、 ちょっと改善したバージョンを時間があれば追記したい。

おしまい。

参考

• pep8 - Python コードのスタイルガイド
• (英語)Wikipedia - Sieve of Eratosthenes
• (英語)MIT - Open Course Ware : 素数計算アルゴリズムいろいろ

変更履歴

• 2020/08/04 初版公開