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 个字符的整数值上。有人可以告诉我为什么这两种情况下的输出不同吗？

4

2 回答 2

10

你想要n % p == 0，没有n % p is 0。 is测试同一性，而不是相等性，并且并非每个 0都与其他每个 0 相同。

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

id那里基本上对应于内存中的一个位置。

这样想：如果你有一个加元，而我有一个加元，那么它们的价值是相等的（1 == 1），但它们不是同一个对象（我的一美元硬币不是和你的一美元硬币一样。）我们可以分享同一个硬币，但我们没有必要这样做。

[PS：您可以使用n//p整数除法而不是int(n/p)。]

于 2013-01-29T21:40:41.057 回答
3

幕后发生的事情有点复杂。我的评论特别适用于CPython. PyPy、Jython、IronPython 等其他实现的行为会有所不同。

为了减少内存使用并提高性能，CPython 缓存了一系列小整数并尝试返回对这些对象的引用，而不是创建另一个具有相同值的整数对象。当您将数字与 进行比较时is，您实际上是在检查 CPython 是否返回了对同一缓存对象的引用。但有时 CPython 不会检查一个值是否是缓存整数之一。这怎么可能发生？

我将解释 CPython 3，因为它比 CPython 2 简单一点。CPythonint中可见的类型实际上是PyLong在解释器内部调用的。PyLong将整数存储为数组，digits其中每个数字介于 0 和2**15-1（32 位系统）或 0 和2**30-1（64 位系统）之间。随着数字变大，数组的大小也会增加；这允许有效地无限整数。在计算 时%，CPython 检查第二个参数是否为一digit长。如果是这样，它会调用一个 C 函数 (divrem1)，该函数返回 adigit作为结果。接下来，PyLong_FromLong调用将适合 C long 的值（即 的返回值divrem）转换为 PyLong。PyLong_FromLong检查参数是否在缓存整数范围内，如果可能，将返回对缓存整数的引用。

如果第二个参数的长度超过一个digit，则调用不同的 C 函数 (x_divrem)。x_divrem使用通用的任意精度除法算法来计算余数。由于在计算过程中x_divrem创建 aPyLong来存储余数，因此避免创建另一个重复整数没有任何好处；它已经存在。对于随机大数的计算，余数很少等于缓存的整数之一，因此不值得花时间进行检查。

还有其他方法可以创建缓存整数的重复副本。我只是从问题中分析了一个。

这就是为什么你不使用is检查数字相等性......

于 2013-01-30T03:44:07.247 回答