正確な結果を得るために Python で素数出力を最適化する方法

Python での一連の素数の出力

素数の識別は数学とプログラミングの基本的な概念です。素数は、2 つの小さい整数の積ではない、1 より大きい整数です。次の Python コードは、1 から 100 までの一連の素数を出力することを目的としています。

コードと問題

素数を見つける一般的なアプローチの 1 つは、数値を反復処理することです。 2からnまで。それぞれの数値について、2 とそれ自体の間の数値 (1 を除く) で割り切れるかどうかを確認します。割り切れる場合、それは素数ではありません。

1 から 100 までの素数を出力することを目的とした次のコードを考えてみましょう。

<code class="python">for num in range(1, 101):
    for i in range(2, num):
        if num % i == 0:
            break
        else:
            print(num)
            break</code>

ただし、このコードでは、素数の代わりに奇数が出力されるという問題が発生します。この欠陥は、外側のループが素数だけでなく合成数 (他の数値の倍数) も反復するために発生します。その結果、条件 if num % i != 0 は 9 のような奇数の合成数に対して true になり、すべての奇数が誤って出力されます。

解決策と最適化

これを修正するには、素数を明示的にチェックするようにコードを変更する必要があります。改訂版は次のとおりです。

<code class="python">for num in range(2, 101):  # Start at 2 as 1 is not prime
    prime = True
    for i in range(2, num):
        if num % i == 0:
            prime = False
    if prime:
        print(num)</code>

このコードでは、最初は True に設定されているブール変数プライムを導入します。次に、内側のループを使用して、2 から num-1 までの各数値 (num を除く) をチェックします。 num が任意の数値 i で割り切れる場合、素数を False に設定し、素数ではないことを示します。内側のループの後、素数が True のままであれば、num.

を出力します。このコードは、指定された範囲内の素数を正確に識別します。ただし、num の平方根までの除数のみをチェックすることでさらに最適化できます。これは、平方根より大きい係数には、対応する平方根より小さい係数があるためです。

最適化されたバージョンは次のとおりです:

<code class="python">for num in range(2, 101):
    prime = True
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            prime = False
    if prime:
        print(num)</code>

これらの調整を使用すると、コードは効果的に出力されます。 1 から 100 までの一連の素数。

以上が正確な結果を得るために Python で素数出力を最適化する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。