2

is_prime次のように bool フラグを使用して、指定された N までの素数を返す単純な python モジュールを作成しました。

def generate_primes_up_to(M):
    n = 2
    primes = []    
    while n <= M:
        is_prime = True
        for p in primes:
            if p**2 > n: break
            if n % p == 0:
                is_prime = False
                break
        if is_prime: primes.append(n) 
        n += 1
    return primes

if __name__ == '__main__':
    generate_primes_up_to(100)

出力：

[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]

これは、ループ内で s が発生しない場合にのみfor-else数nが素数になるため、実際にはこの構造を使用するのに理想的なケースです。したがって、関数を次のように変更しました。breakfor

def generate_primes_up_to(M, flag='nonumpy'):
    n = 2
    primes = []    
    while n <= M:
        for p in primes:
            if p**2 > n: break
            if n % p == 0: break
        else: primes.append(n) 
        n += 1
    return primes

しかし今、コードは次のように出力します:

[2, 5, 27]

式が句if p**2 > n: breakの流れを妨げている理由がわかりません。for-elseその行を削除すると、コードは正しい出力を再び生成します。

4

2 に答える 2

4

問題の原因となる条件は -

if p**2 > n: break

例を見てみましょう - 7、 7 が素数かどうかをチェックしているとき、 - が素数であることは既にわかっています。上記の条件はループを[2,3,5]破り、=が より大きいとチェックします。for33**297

その条件を削除すると、正常に動作します (非常に遅いですが)。

元のループ (for-else コンストラクトなし) では、ループから抜け出したばかりでフラグを変更しなかったため、機能しましたis_prime。

for..elseコンストラクトを使用すると、ステートメントを使用せずにループを終了したときにのみ、その部分がelse実行されます。break

ただし、上記の条件の場合、breakステートメントを使用するため、else一部は実行されません。

于 2015-08-02T08:47:25.443 に答える
1

以下も使用できますnext。

def generate_primes_up_to(M):
    n = 2
    primes = []
    while n <= M:
        if next((False for p in primes if not n % p), True):
            primes.append(n)
        n += 1

    return primes
于 2015-08-02T10:56:24.113 に答える