Python displaying ints as long?

Question

So here are two functions for finding the prime factors of a number. Credits: Triptych https://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]

In the second version, you're appending `n`, which is a long. — , May 28 '16 at 20:58
This is what I'm using: Jupyter QtConsole 4.2.0. Python 2.7.11 |Anaconda 4.0.0 (64-bit)| IPython 4.1.2 — Kevin, May 28 '16 at 21:05
On Windows 10 64-bit: `65126264424 > sys.maxint` returns True, on Ubuntu 12.04 64 bit it returns False. — ayhan, May 28 '16 at 21:56

user2390182 · Accepted Answer · 2016-05-28T23:09:30.723

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:

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

Python displaying ints as long?

1 Answers1