Terms used in general
def of prime numbers
まずは素数の簡単な理解から（より正確な定義はwikiなどを）
- 1より大きい
- その数と1でしか割り切れない
という２つの定義を使って処理を行っていく。
Sieve of Eratosthenes
より効率的に素数を出すことの出来るアルゴリズム。一言で説明するとn番目までの数字上で（上で定義した共通点を元に）共通の仲間を除外していく。除外されていない数字全てが素数。（簡略化されたmachine learning的な。。。）より具体的な説明は以下とwikiを参考に。
implementation in Python
一番最初に考えていたのはdictionaryをベースに毎回membership判定を行なうgeneratorなり関数を作る。
def prime_gen():
"self-explanatory prime generator"
D = {}
q = 2
while True:
if q not in D:
yield q
D[q*q] = [q]
else:
for p in D[q]:
D.setdefault(p + q, []).append(p)
del D[q]
q += 1
def nth(iterable, n, default = None):
"Returns the nth item or a default value"
return next(islice(iterable, n, None), default)
こちらのタイプは先に何番目までの素数が欲しいのかを予め決めておき、その数字にたどり着くまでひたすら処理を行い続けるタイプのgenerator。limitの数分だけTrue valを用意しておきfor loopで引っかかった数字を少しずつFalseに変えていく。よってyieldされるのはTrueとされているvalのリスト内のポジションが値として返ってくる。
def primes_sieve2(limit):
a = [True] * limit # Initialize the primality list
a[0] = a[1] = False
for (i, is_prime) in enumerate(a):
if is_prime:
yield i
for n in range(i*i, limit, i): # Mark factors non-prime
a[n] = False
具体的な例を兼ねて説明すると;
例えばprime_nums = primes_sieve2(100)。
- 100個のTrue valが入ったリストが作られ最初の2のbooleanがFalseに変換。（最初の0と1は素数ではないので）
- for loopとenumerateを使って整理。iが実際の数字でis_primeは文字通り素数かそうでないかのフラッグとしての役割を果たしている。もしis_prime = Trueならばその数字が出力される。
- yieldした後はgeneratorの法則に従ってyield下にあるfor loopから処理が始まる。ここでは上で軽く触れた「n番目までの数字上で（上で定義した共通点を元に）共通の仲間を除外していく」という作業を行っている。iをlimitにぶつかるまでひたすらスケールしていきその度にその数字のis_prime valをFalseへと変えていく。
- その処理を終える毎にval whose is_prime = Trueがyieldされていく。
こちらのimplementationは個人的に感動した。無駄なvalが何一つなく綺麗に再利用されていく様が見える。
sievesに関しては実に様々な処理方法がありそれぞれ処理速度が変わってくるので一番効率的な関数は別途探せば出てくると思われる。基本的な違いはいつどこでどの処理をするかが違うだけであって基本的なアルゴリズムの構造は変わらない。その辺に関してはこの記事がjump startになるかもしれない。sieveのoptimizationに関してはこちら