Renegade - 8 months ago 17

Python Question

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:

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

.