●
って、またpythonかよ。最近はホントpythonの波がきてる。
例によってプログラミング問題。今回は「与えられた数nまでの素数を列挙する」。最初に言ってしまうと今回のスクリプトは完全に俺の自力作ってわけじゃない。はじめに書いたものは以下のような仕組みだった。
# 1. [2〜n]のリストを作る。
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... n]
# 2. 下から順番に素数かどうかチェックする。2からその数までの数で割ってみて、割り切れなかったら素数である。
[2(素数だッ), 3(素数だッ), 4, 5, 6, 7, 8, 9, 10, 11, ... n]
# 3. 素数確定したら、リストからその数の倍数を全部削除していく。
[2(素数だッ), 3(素数だッ), , 5, , 7, , , 10, 11, ... n]
完成はしたのだけど、知り合いが言い出した。
「これ2〜nまで全部そのチェックしてんの? nの平方根まででよくない?」
マジで? nが100だったら10までチェックすればいいってこと? なんで?
これの理解に時間を使っちゃったんだが、知り合いの根気強い解説もありなんとか以下のような理解ができた。
- 2から平方根数までは上述の俺の発想で問題ない。
- 「平方根より上はチェック必要ないよ」と言われて俺が疑問なのは、「平方根より上の素数の倍数が残ってたらどうすんの?」ってことだ。でもそれが杞憂だったんだよ。
- なぜかといえば、平方根より上の数の倍数で、かつnまでに収まる数を作るには平方根未満の数を相方に使わないといけないからだ。そして平方根未満の数の倍数については上述のチェックで終了している。
- どっちも平方根を超えた数だったら、nより大きい数になっちゃう。その数は対象外だから問題ない。
- よって、俺が心配していた「平方根より上の素数の倍数」はチェック済み、または対象外ということになる。なーんだ!
n=25としたときの具体例で復習してみる。
2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
- 2から5までは上述の俺の発想で問題ない。
- 6から上の数の倍数で、かつ25までに収まる数を作るには5未満の数を相方に使わないといけない。そして2,3,4の倍数については上述のチェックで終了しているから問題ない。
- どっちも平方根を超えた数、6以上だったら、25より大きい数になっちゃう。その数は対象外だから問題ない。
●
というわけで完成した回答がこれ。
# get_primes.py
from math import sqrt
def get_primes(n):
'''2からnまでの素数を求めます。'''
# boolスイッチ。素数じゃないもののスイッチをFalseにしていきます。
switches = [b > 1 for b in range(n+1)]
# 素数チェックはnの平方根まででOK。
for i in range(int(sqrt(n))+1):
# スイッチがFalseのものは、0,1,または下の倍数スイッチオフの対象になったものです。
if switches[i] is False:
continue
# 素数を残しつつ、その倍数のスイッチをFalseにしていきます。
j = i * 2
while j <= n:
switches[j] = False
j += i
# スイッチがTrueのものが素数です。
return [i for i in range(len(switches)) if switches[i] is True]
実行結果。素数のプログラムは速ければ速いほど良いというので時間も出してみた。
import time
# 計測開始。
start = time.time()
# 実行。
import get_primes
print(len(get_primes.get_primes(100000)))
# 計測結果。
my_time = time.time() - start
print(f'my_time : {my_time}')
#
# 9592 (2～100000間の素数の数)
# my_time : 0.031523704528808594 (かかった秒数)
#
