特定の値まで素数を生み出すアルゴリズム in Python3



特定の値まで素数を生み出すアルゴリズムとか

以下のようにリストで真偽値を管理するやり方で書くといいらしい。


Elements of Programming Interviews in Python より。

# Given n, return all primes up to and including n.
def generate_primes(n):
    primes = []
    is_prime = [False,False] + [True] * (n-1)
    for p in range(2,n+1):
        if is_prime[p]:
            primes.append(p)
            for i in range(p*2,n+1,p):
                is_prime[i] = False
    return primes

n = 100
print(generate_primes(n)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

コメント

このブログの人気の投稿

Braveブラウザの同期機能をiPhoneで設定した話。

JavaのindexOf関数はナイーブ法で実装されているらしい

C++のstd::lower_bound()とPythonでの話。