python - 素数チェック Python

Question

私はこの非常に単純な素数チェックを書きました:

prime = int(input())
if prime % prime == 0 and prime % 2 != 0 and prime % 3 != 0 or prime == 2 or prime == 3:
    print("true")
else:
    print("false")

...何とか機能しているようですが、正しい方法かどうかはわかりません。誰か確認してください。

Answer 1

それが得られるのと同じくらい簡単です：

def isprime(n):
    """check if integer n is a prime"""
    # range starts with 2 and only needs to go up the squareroot of n
    for x in xrange(2, int(n**0.5)+1):
        if n % x == 0:
            return False
    return True

印象的な素数ジェネレータについては、こちらを参照してください

Answer 2

それが正しい方法かどうかはわかりません

そうではありません。反例を一つあげると、それ25は素数だと思います。さらに悪いことに、そのような反例は無数にあります。

ウィキペディアは、これを行うためのさまざまな (正しい) 方法について読む価値があります。

Answer 3

素数性に関するウィキペディアの記事は、より優れたアルゴリズムを設計するのに役立ちます。それらはたくさんありますが、基本的なものはそれほど複雑ではありません。

• まず、素数は 1 より大きい正の整数でなければならないという事実から離れてください。この不変条件は、n < 2 の場合、すぐに false を返す可能性があることを意味します。あなたのコードでは、n=0 は失敗します。
• 単純なアプローチでは、1 から n までの n のすべての約数をチェックするように移動できます。2 つ見つけられれば、それが素数であることがわかります。
• より直感的なアプローチは、すべての数が 1 とそれ自体で割り切れると結論付けることです。そのため、2 と n-1 の間でのみ約数をチェックできます。n の約数を見つけた瞬間に、n は素数ではないと結論付けることができます。
• 改善されたアプローチでは、すべての偶数が 2 で割り切れることが認識されるため、n が 2 で割り切れない場合、それ以降は奇数の約数のみを確認できます。
• 最後に、n までのすべての約数をチェックする必要はありません。n の平方根まで除数をチェックすれば十分です。そのしきい値に達したときに除数が見つからない場合は、n が素数であると結論付けることができます。