Python を使用して素数判定アルゴリズムを実装するにはどうすればよいですか?

Python を使用して素数判定アルゴリズムを実装するにはどうすればよいですか?

素数とは、2、3、5、7 など、1 とそれ自体でのみ割り切れる正の整数を指します。素数の決定は一般的なアルゴリズムの問​​題です。この記事では、Python を使用して簡単で効率的な素数決定アルゴリズムを作成する方法を紹介します。

まず、素数を判断するための条件を明確にする必要があります。正の整数 n について、n が k で割り切れるような 2

次に、素数判定アルゴリズムを実装するコードを記述します。以下は、Python で書かれたサンプル コードです。

import math

def is_prime(n):
    # 排除小于2的数
    if n < 2:
        return False
    
    # 循环判断2到sqrt(n)之间的数是否能整除n
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    
    # 如果没有找到能整除n的数，则n是素数
    return True

# 测试示例
print(is_prime(2))    # 输出：True
print(is_prime(3))    # 输出：True
print(is_prime(4))    # 输出：False
print(is_prime(17))   # 输出：True
print(is_prime(18))   # 输出：False

上記のコードでは、まず、sqrt 関数を使用して n の平方根を計算する数学モジュールを導入します。次に、正の整数 n をパラメータとして受け取る is_prime 関数を定義します。

is_prime 関数内では、まず 2 未満の数値を除外します。これは、素数の定義によれば、素数は 2 以上でなければならないためです。次に、ループを使用して、n が 2 から sqrt(n) までの範囲で割り切れるかどうかを判断します。 n を割る数値が見つかった場合、つまり n が素数ではない場合は、すぐに False を返します。ループ終了後に n を均等に分割できる数が見つからない場合、n は素数であるため、True を返します。

最後に、is_prime 関数を呼び出して例をテストできます。さまざまなパラメータを入力すると、正しい素数判定結果が表示されます。

もちろん、上記のコードは素数判定を実装するための単純なアルゴリズムです。大きな数の素数判定については、Erathosthenes Sieve などのより効率的なアルゴリズムがあります。読者はこれらのアルゴリズムをさらに学び、探索して、より効率的な素数判定を達成することができます。

以上がPython を使用して素数判定アルゴリズムを実装するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。