Renegade - 4 months ago 5x
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]
``````

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`?

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`.