1以上100未満の『2個の素数の積』である整数
Python Hack-a-thon#1 の参加フォームに
問題: 1以上100未満の『2個の素数の積』である整数を列挙しなさい （回答は任意です）
という問題があったのでやってみました。
Generatorだけを使っているので無駄にリストを作ってメモリを使いすぎないようにしています。limitを100000くらいにしても割と普通に動きます。
ただ、2回目のLoopで素数の計算を何度もやっているのが無駄、、、GeneratorはDeepcopyや、一つ前に戻すのが難しい、、、itertools.teeでも上手くかけませんでした orz...... 1以上100未満の『2個の素数の積』である整数
import math
from itertools import ifilter, count
limit = 100
def sieve(limit=None, start=2):
g = count(2)
g = ifilter(lambda x, start=start: x >= start, g) #start以上の素数を返すFliter
while True:
prime = g.next()
if limit and prime > limit: # limitを超えたらStopIteration
raise StopIteration
yield prime
g = ifilter(lambda x, prime=prime: x % prime, g) # primeで割り切れるとFalse、割り切れないとTrueを返すlambdaをフィルターに追加
for i in sieve(int(math.sqrt(limit))): # limit が100なら 10がlimit
for k in sieve(limit/i, i):
print "%s * %s = %s" % (i, k, (i*k))
素数に関しては以前書いたEntryとおり、4 TopCoderさんのGeneratorを使っています。
この素数ジェネレーターは今まで見てきたPythonのコードの中でもかなり良いと思うコードなので、何をしてるか分からない人はリンク先の解説を見るといいでしょう。
今回は引数limitでStopIteration、引数start以上の数を返すフィルターを追加しました。
素数の積なので、たとえば 2,3,5で考えると
| 2*2 | 2*3 | 2*5 |
| 3*2 | 3*3 | 3*5 |
| 5*2 | 5*3 | 5*5 |
の計算をしなくてはいけません、しかし、2*3 と3*2は同じ値になるので、一度だけ計算すればOKです。
| 2*2 | 2*3 | 2*5 |
| 3*3 | 3*5 | |
| 5*5 |
よって、2回目のループは 最初のループの値 i以上の数値にすれば重複しないで済むので、素数のGeneratorに追加した引数startにiを渡してあげます。
次に、2回目のループをどこまで計算するかですが、1回目のループ i * k が limit (100)以上の場合は不要になります。よって limit(100) / iまでやればOKです。
最後に最初のループをどこまでやるかです、、、
これは先ほどの 2, 3, 5の例をみれば k >= iの場合、 常に最初の i * k は i * iと同じになるので i*iが100以内になるような数、10まで計算すればOKということになります。これをpythonで汎用的に書くと int(math.sqrt(limit)) ということになります。
10 * 10 = 100なんだから、11 * 11は100以上になるから計算の無駄ということですね。
結果
2 * 2 = 4
2 * 3 = 6
2 * 5 = 10
2 * 7 = 14
2 * 11 = 22
2 * 13 = 26
2 * 17 = 34
2 * 19 = 38
2 * 23 = 46
2 * 29 = 58
2 * 31 = 62
2 * 37 = 74
2 * 41 = 82
2 * 43 = 86
2 * 47 = 94
3 * 3 = 9
3 * 4 = 12
3 * 5 = 15
3 * 7 = 21
3 * 11 = 33
3 * 13 = 39
3 * 17 = 51
3 * 19 = 57
3 * 23 = 69
3 * 29 = 87
3 * 31 = 93
5 * 5 = 25
5 * 6 = 30
5 * 7 = 35
5 * 8 = 40
5 * 9 = 45
5 * 11 = 55
5 * 13 = 65
5 * 17 = 85
5 * 19 = 95
7 * 7 = 49
7 * 8 = 56
7 * 9 = 63
7 * 10 = 70
7 * 11 = 77
7 * 12 = 84
7 * 13 = 91
