3
def test_prime(n):
    q = True
    for p in range(2,n):  #Only need to check up to rootn for primes and n/2 for factors
        if int(n%p) is 0:         
            q = False
            print(p, 'and', int(n/p), 'are factors of ', n)    
    if q:
        print(n, 'IS a prime number!')
    else:
        print(n, 'IS NOT a prime number')

私は Python をいじり始めたばかりで、時間をつぶすためにいくつかの断片をまとめています。私は素数のテストで遊んでいて、非素数の因数を示すという考えを持っていました。上記でまとめた関数は、一貫性のない出力が得られることを除いて、十分に機能しているようです。

たとえば、n = 65432 に設定すると...

2 and 32716 are factors of  65432
4 and 16358 are factors of  65432
8 and 8179 are factors of  65432
8179 and 8 are factors of  65432
16358 and 4 are factors of  65432
32716 and 2 are factors of  65432
65432 IS NOT a prime number

それは私が期待するものです。しかし、n = 659306 に設定すると...

2 and 329653 are factors of  659306
71 and 9286 are factors of  659306
142 and 4643 are factors of  659306
4643 and 142 are factors of  659306
9286 and 71 are factors of  659306
659306 IS NOT a prime number

最後に係数 329653 が含まれていないため、これは異なります。すべての要因がどこかに表示されるので、これは問題ではありませんが、いくつかの数値でなぜこれが起こるのか分からないのは私を悩ませています!

私が完全なバカではないことを示すために、これは長さが 5 文字を超える整数値でのみ発生するように思われることを突き止めました。これら2つのケースで出力が異なる理由を教えてください。

4

2 に答える 2

10

あなたがしたいn % p == 0、ではありませんn % p is 0is等しいかどうかではなく同一性をテストし、すべての 0他のすべての 0 と同じであるとは限りません。

>>> 659306 % 329653
0
>>> (659306 % 329653) == 0
True
>>> (659306 % 329653) is 0
False
>>> id(0)
136748976
>>> id(659306 % 329653) 
3070888160

そこidは基本的にメモリ内の場所に対応します。

このように考えてみてください: あなたがルーニーを持っていて、私がルーニーを持っている場合、それらは互いに値が等しい (1 == 1) ですが、それらは同じオブジェクトではありません (私の 1 ドル硬貨は同じコインを共有することもできますが、必ずしもそうする必要はありません。

[PS:n//pの代わりに整数除算に使用できますint(n/p)。]

于 2013-01-29T21:40:41.057 に答える
3

舞台裏で起こっていることは少し複雑です。私のコメントは特にCPython. PyPy、Jython、IronPython などの他の実装では、動作が異なります。

メモリ使用量を減らしてパフォーマンスを向上させるために、CPython は一連の小さな整数をキャッシュし、同じ値を持つ別の整数オブジェクトを作成する代わりに、これらのオブジェクトへの参照を返そうとします。数値を と比較するとis、CPython が同じキャッシュされたオブジェクトへの参照を返したかどうかを実際に確認しています。しかし、値がキャッシュされた整数の 1 つであるかどうかを CPython がチェックしないことがあります。これはどのように起こりますか?

CPython 2 よりも少し簡単なので、CPython 3 について説明します。CPython でint表示される型は、実際にはPyLong内部でインタープリターに呼び出されます。各桁が 0 ~(32 ビット システム) または 0 ~(64 ビット システム)PyLongの配列として整数を格納します。数値が大きくなるにつれて、配列のサイズが大きくなります。これにより、事実上無制限の整数が可能になります。を計算するとき、CPython は 2 番目の引数が 1 つの longかどうかをチェックします。その場合、結果として a を返す C 関数 (divrem1) を呼び出します。次に、C の long に収まる値 (つまり の戻り値) を PyLong に変換するために が呼び出されます。digits2**15-12**30-1%digitdigitPyLong_FromLongdivremPyLong_FromLong引数がキャッシュされた整数の範囲内にあるかどうかをチェックし、可能であればキャッシュされた整数への参照を返します。

2 番目の引数が複数のdigit長さの場合、別の C 関数 (x_divrem) が呼び出されます。x_divrem汎用の任意精度除算アルゴリズムを使用して剰余を計算します。は計算中に剰余を格納するためにx_divremを作成するPyLongため、別の重複した整数の作成を回避しても利点はありません。それはすでに存在します。ランダムな大きな数値を使用した計算の場合、剰余がキャッシュされた整数の 1 つと等しくなることはめったにないため、チェックに時間をかける価値はありません。

キャッシュされた整数の複製コピーを作成する方法は他にもあります。私はちょうど質問からのものを分析しました。

これが、数値の等価性のチェックに使用しない理由ですis.....

于 2013-01-30T03:44:07.247 に答える