0

私はそれが何度も議論されてきたことを知っています。読んだのですが、どういうわけかわかりません。入力した数が素数かどうかを判断するプログラムを書きたい。

私がインターネットのどこかで見つけた実装の1つ：

from math import *

def main():
    n = abs(input("Enter a number: "))
    i = 2
    msg = 'is a prime number.'
    while i <= sqrt(n):
        if n % i == 0:
            msg = 'is not a prime number.'
        i = i + 1
    print n, msg


main()

ここにいくつかの質問があります：

  • 上記ではi、とは何ですか。また、開始値がなぜ2ですか。
  • i = i + 1このプログラムでは何をしますか？
  • 'is a prime number.'インタプリタは、ボディループの外にある場合でも、いつ印刷するかをどのように知るのですか？
4

2 に答える 2

4

素数は、1とそれ自体でのみ割り切れる数です。n使用している方法は、候補番号を2からそれ自体までの1つおきの番号で割ってみることです。ただし、いずれかiの数があなたの数の約数である場合nはそうでn / iあり、それらの少なくとも1つは以下であるため、包括的までsqrt(n)テストするだけで済みます。sqrt(n)実際には、実際に素数である除数をテストするだけで済みますが、手に入れる素数のリストがないため、すべてをテストします。

上記の何iですか？そして、なぜそれが2の開始値を得たのですか？

in私たちがテストしている潜在的な要因です。n素数の定義がそれを許可/期待しているので、1が分割されるかどうかは気にしないので（そして自明にそうなるので）、2で始まります。

この具体的な例では、i = i + 1ステートメントは何ですか？プログラムでの使用がわかりません。

;iで定義されたループの最後で値をインクリメントします。これは、の次の候補除数のテストwhile i <= sqrt(n)に進むことを意味します。in

そして最後に、Pythonがいつ印刷するかを知る方法は「素数」です。それは体のループの外にありますが？

初期化msgして「素数です」とし、除数が見つかった場合は、ループ内で「素数ではありません」に変更します。ループで除数が見つからない場合、またはループが実行されない場合は、設定した初期値である「素数」を使用します。ちなみにbreak、除数を見つけたときにループから外れる可能性があります。その後、テストを続ける意味はありません。

もう1つは別としてsqrt(n)、whileの外で計算し、変数で使用するよりも格納したいwhile場合があります。反復ごとに平方根を再計算する場合がありますが、これは比較的コストがかかります。

于 2013-02-05T14:38:15.250 に答える
2

各行の機能を説明するために、側面にコメントを追加しました。

from math import * # imports everything from the math module

def main():
    n = abs(input("Enter a number: ")) # gets input from the user
    i = 2 # starts off at 2 because all input is divisble by 1
    msg = 'is a prime number.' # the message is initially set
    while i <= sqrt(n):
        if n % i == 0: # if 'i' divides evenly into n
            msg = 'is not a prime number.' # only set if it isn't a prime
        i = i + 1 # increases 'i' by 1 so it can check every value up to the square-root of 'n' (to see if it divides evenly)
    print n, msg


main()

プログラムは、すべての可能な要素がチェックされるようiに、（の平方根までの）のすべての値を調べる必要があります。n

これは一種の大まかな素数チェッカーであり、素数ではない大きな数の場合は非効率的です。入力がのような数の場合、1234567890その数の平方根まですべての数を繰り返し処理します。これは35147（切り上げ）です。 。ステートメントを使用returnするとループが中断されるため、最初にチェックする数値は2、で割り切れるため、素数ではないと宣言され2ます。を使用returnすると、関数が停止し、35,146回の計算が節約されます。これは（少なくともコンピュータにとっては）膨大な数ではありませんが、それでもメモリ効率が高く、時間もかかりません。

def isPrime(n):
    '''Checks if 'n' is prime.'''
    from math import sqrt
    if n == 0 or n == 1:
        return False
    else:
        for check in range(2, int(sqrt(n))+1):
            if n % check == 0: return False
    return True
于 2013-02-05T15:09:46.627 に答える