Hatena::Grouppython

Pythonで遊ぶよ

 | 

2009-05-11

「1以上100未満の『2個の素数の積』である整数を列挙しなさい」

18:12

こちらの記事を見ておもしろそうだったのでやってみた。

#!/usr/local/python

def primes_upto(N):
    def sieve(list):
        if not list: return []
        else: return [list[0]] + sieve([n for n in list[1:] if n % list[0] != 0])
    return sieve(range(2,N+1))

def getPrim0(N):
    primes = primes_upto(N//2)
    return sorted([x*y for x in primes for y in primes if x < y and x*y <= N])

def main():
    print getPrim0(100)

if __name__ == '__main__':
    main()

結果。

[6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95]

リスト内包表記のワンライナーでやれと言われたら別の方法でやるかな。

def getPrim1(N):
    return [n for n in range(2,N+1)
            if len(
                [p for p in range(2,n)
                    if n % p == 0 and
                    len([d for d in range(2,p) if p % d==0])==0 and
                    len([d for d in range(2,n//p) if (n//p) % d==0])==0
                ]) == 2
            ]   

↑どうやっても綺麗には書けないw

内側から見ていくと、まず

len([d for d in range(2,p) if p % d==0])==0

これが、p が素数である条件となる。

if n % p == 0 and
len([d for d in range(2,p) if p % d==0])==0 and
len([d for d in range(2,n//p) if (n//p) % d==0])==0

この部分で、n が p で割れる、かつ、p が素数である、かつ、n/p が素数である条件。これを仮に条件 "A" とする。

次の部分、

len([p for p in range(2,n) if 条件 "A" ])==2

これは、2 から n までの数 p で、条件 "A" にあてはまる p の数がちょうど2個ある条件。仮に条件 "B" とする。

最後に、

[n for n in range(2,N+1) if 条件 "B"]

N 以下の数のうち、条件 "B" に合う n を全部。


一応測定

N = 100
t0 = time.time()
print getPrim0(N)
t1 = time.time()
print t1-t0

t0 = time.time()
print getPrim1(N)
t1 = time.time()
print t1-t0

t0 = time.time()
print getPrim2(N)
t1 = time.time()
print t1-t0
# 一番上の getPrim0
[6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95]
0.000253915786743

# オレオレワンライナー getPrim1
[6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95]
0.00280594825745

# a2c さんの getPrim2
[4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95]
0.0440678596497

a2c さんのほうは「同じ2つの素数の積」も計算してるんだね。僕のほうは「違う2個の素数」と考えたのでちょっと条件が違うか。

でも速度は1桁勝った。やたー。

a2ca2c2009/05/11 18:48二つの素数の積の理解は、http://ja.wikipedia.org/wiki/%E5%8D%8A%E7%B4%A0%E6%95%B0ここに、同じのも2乗(prim^2)してたのでそれを採用しました。
にしても、全然スピード違いますね。無駄に同じ事2回してるのが駄目ぽい。

edvakfedvakf2009/05/11 22:26それを言ったら僕のワンライナーもエラトステネスのふるいを使ったアルゴリズムより1桁遅いですから、50歩100歩といいますかなんといいますか。

getPrim2 の 2 が自乗の 2 だと今知ったのは秘密です。(汗

トラックバック - http://python.g.hatena.ne.jp/edvakf/20090511
 |