CODEWITHSUNDEEP
pythonpython-2.7long-integer
Kevin
Kevin

Reputation: 1085

Python displaying ints as long?

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]

Upvotes: 2

Views: 85

Answers (1)

user2390182
user2390182

Reputation: 73450

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.

Upvotes: 4

Related Questions