Renegade Renegade - 6 months ago 8
Python Question

Python displaying ints as long?

So here are two functions for finding the prime factors of a number.
Credits: Triptych
http://stackoverflow.com/a/412942/6211963

def prime_factors1(n):
"""Returns all the prime factors of a positive integer"""
factors = []
d = 2
while n > 1:
while n % d == 0:
factors.append(d)
n /= d
d = d + 1

return factors

def prime_factors2(n):
"""Returns all the prime factors of a positive integer"""
factors = []
d = 2
while n > 1:
while n % d == 0:
factors.append(d)
n /= d
d = d + 1
if d*d > n:
if n > 1: factors.append(n)
break
return factors


Obviously the second code runs a lot faster, but why does it output the largest factor as long-type rather than int?

>>> prime_factors1(65126264424)
[2, 2, 2, 3, 13, 29, 7197863]

>>> prime_factors2(65126264424)
[2, 2, 2, 3, 13, 29, 7197863L]

Answer

The difference is the following. In prime_factors1(n), the last factor is appended here:

while n > 1:
    while n % d == 0:
        factors.append(d)

where d starts out at 2 (definitely an int no matter which runtime), grows via d = d + 1 (addition of two int) and - when it is appended as a factor - stands at 7197863 (still an int).

In prime_factors2(65126264424), however, you append the last factor here:

if d*d > n:
    if n > 1: factors.append(n)

where n starts out at 65126264424 and shrinks via n /= d. This will not change the type of n if it starts out as a long (if n is a long and d is an int, the result will still be a long no matter how small). The question therefore becomes: Is 65126264424 a long?

The answer depends on your python runtime:

  1. In a 32-bit runtime, you typically have 32-bit integers that max out at (2**31 - 1) or 2147483647 which is smaller than 65126264424.
  2. In a 64-bit runtime, you typically have 64-bit integers that max out at (2**63 - 1) or 9223372036854775807 which is bigger than 65126264424.

See the output of sys.maxint and it should be smaller than 65126264424.