generatorで無限に素数を生成する – 日曜研究室

2010/12/5 日曜日

peta_okechan

Take it easy!

いろんなところでやり尽くされてる感があるネタですが、とりあえず自分なりに普通に書いてみたらそこそこ速かった。

def is_prime(n, primes):
    for p in primes:
        if p * p > n:
            primes.append(n)
            return True
        elif n % p == 0:
            return False
    primes.append(n)
    return True

def prime_generator():
        primes = []
        n = 1
        while True:
            n += 1
            if is_prime(n, primes):
                yield n

さっとググって出てきたこれと比較してみたら、
100までの素数を求める処理では、今回のもののほうが1.5倍遅く、
10000まででは、今回のもののほうが1.5倍速く、
100000まででは、今回のもののほうが3倍速かった。

コメントを残す

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。