技術

generatorで無限に素数を生成する

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

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 を使っています。コメントデータの処理方法の詳細はこちらをご覧ください