Nodachisoft Nodachi Sword Icon
  
@あまじ✎ 2020年8月4日に更新

python で素数を計算する

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

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

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

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

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

動作確認済み環境

  • python 2.7.15、3.8.5

コード

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

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

 
get_primelist.py
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 コマンドで実行し結果表示まで含めた時間です。

計算する素数の幅 計算時間(3回の平均)
1~100 0.03 秒
1~1,000 0.03 秒
1~10,000 0.29 秒
1~100,000 22.55 秒

計測した環境

  • 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

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

高速化メモ

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

おしまい。

参考

変更履歴

  • 2020/08/04 初版公開
 
 
送信しました!

コメント、ありがとうございます。

なんかエラーでした

ごめんなさい。エラーでうまく送信できませんでした。ご迷惑をおかけします。しばらくおいてから再度送信を試していただくか、以下から DM などでご連絡頂ければと思います。

Twitter:@NodachiSoft_jp
お名前:
 
連絡先:
 
メッセージ:
 
戻る
内容の確認!

以下の内容でコメントを送信します。よろしければ、「送信」を押してください。修正する場合は「戻る」を押してください

お名前:
 
連絡先:
 
メッセージ:
 
Roboto からの操作ではないという確認のため確認キーを入れてください。
確認キー=95
戻る
 / 
送信確認へ
コメント欄
コメント送信確認へ

関連ありそうな記事(2件)です!

Python でファイルをまとめて別のフォルダに移動したりコピーしたりする

#Python#コードスニペット✎ 2020-10-21
Python を使ってファイルをまとめて別のフォルダに移動するプログラム
広告領域
追従 広告領域
目次
python で素数を計算する
python で素数を計算する
動作確認済み環境
動作確認済み環境
コード
コード
RUN
RUN
結果で 以下の 100 までの素数が配列で得られる
結果で 以下の 100 までの素数が配列で得られる
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
[ 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 ]
43,47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 ]
ご参考・処理時間等
ご参考・処理時間等
計測した環境
計測した環境
高速化メモ
高速化メモ
参考
参考
変更履歴
変更履歴
Nodachisoft © 2020