Long integers:
There is no explicitly defined limit. The amount of available address space forms a practical limit.
(Taken from this site). See the docs on Numeric Types where you'll see that Long integers have unlimited precision. In Python 2, Integers will automatically switch to longs when they grow beyond their limit:
>>> import sys
>>> type(sys.maxsize)
<type 'int'>
>>> type(sys.maxsize+1)
<type 'long'>
for integers we have
maxint and maxsize:
The maximum value of an int can be found in Python 2.x with sys.maxint. It was removed in Python 3, but sys.maxsize can often be used instead. From the changelog:
The sys.maxint constant was removed, since there is no longer a limit to the value of integers. However, sys.maxsize can be used as an integer larger than any practical list or string index. It conforms to the implementation’s “natural” integer size and is typically the same as sys.maxint in previous releases on the same platform (assuming the same build options).
and, for anyone interested in the difference (Python 2.x):
sys.maxint The largest positive integer supported by Python’s regular integer type. This is at least 2**31-1. The largest negative integer is -maxint-1 — the asymmetry results from the use of 2’s complement binary arithmetic.
sys.maxsize The largest positive integer supported by the platform’s Py_ssize_t type, and thus the maximum size lists, strings, dicts, and many other containers can have.
and for completeness, here's the Python 3 version:
sys.maxsize An integer giving the maximum value a variable of type Py_ssize_t can take. It’s usually 2^31 - 1 on a 32-bit platform and 2^63 - 1 on a 64-bit platform.
floats:
There's float("inf") and float("-inf"). These can be compared to other numeric types:
>>> import sys
>>> float("inf") > sys.maxsize
True
Long integers:
There is no explicitly defined limit. The amount of available address space forms a practical limit.
(Taken from this site). See the docs on Numeric Types where you'll see that Long integers have unlimited precision. In Python 2, Integers will automatically switch to longs when they grow beyond their limit:
>>> import sys
>>> type(sys.maxsize)
<type 'int'>
>>> type(sys.maxsize+1)
<type 'long'>
for integers we have
maxint and maxsize:
The maximum value of an int can be found in Python 2.x with sys.maxint. It was removed in Python 3, but sys.maxsize can often be used instead. From the changelog:
The sys.maxint constant was removed, since there is no longer a limit to the value of integers. However, sys.maxsize can be used as an integer larger than any practical list or string index. It conforms to the implementation’s “natural” integer size and is typically the same as sys.maxint in previous releases on the same platform (assuming the same build options).
and, for anyone interested in the difference (Python 2.x):
sys.maxint The largest positive integer supported by Python’s regular integer type. This is at least 2**31-1. The largest negative integer is -maxint-1 — the asymmetry results from the use of 2’s complement binary arithmetic.
sys.maxsize The largest positive integer supported by the platform’s Py_ssize_t type, and thus the maximum size lists, strings, dicts, and many other containers can have.
and for completeness, here's the Python 3 version:
sys.maxsize An integer giving the maximum value a variable of type Py_ssize_t can take. It’s usually 2^31 - 1 on a 32-bit platform and 2^63 - 1 on a 64-bit platform.
floats:
There's float("inf") and float("-inf"). These can be compared to other numeric types:
>>> import sys
>>> float("inf") > sys.maxsize
True
Python long can be arbitrarily large. If you need a value that's greater than any other value, you can use float('inf'), since Python has no trouble comparing numeric values of different types. Similarly, for a value lesser than any other value, you can use float('-inf').
In old (2.x) versions of Python, xrange can only handle Python 2.x ints, which are bound by the native long integer size of your platform. Additionally, range allocates a list with all numbers beforehand on Python 2.x, and is therefore unsuitable for large arguments.
You can either switch to 3.x (recommended), or a platform where long int (in C) is 64 bit long, or use the following drop-in:
import itertools
range = lambda stop: iter(itertools.count().next, stop)
Equivalently, in a plain form:
def range(stop):
i = 0
while i < stop:
yield i
i += 1
This is what I would do:
def prime_factors(x):
factors = []
while x % 2 == 0:
factors.append(2)
x /= 2
i = 3
while i * i <= x:
while x % i == 0:
x /= i
factors.append(i)
i += 2
if x > 1:
factors.append(x)
return factors
>>> prime_factors(600851475143)
[71, 839, 1471, 6857]
It's pretty fast and I think it's right. It's pretty simple to take the max of the factors found.
2017-11-08
Returning to this 5 years later, I would use yield and yield from plus faster counting over the prime range:
def prime_factors(x):
def diver(x, i):
j = 0
while x % i == 0:
x //= i
j += 1
return x, [i] * j
for i in [2, 3]:
x, vals = diver(x, i)
yield from vals
i = 5
d = {5: 2, 1: 4}
while i * i <= x:
x, vals = diver(x, i)
yield from vals
i += d[i % 6]
if x > 1:
yield x
list(prime_factors(600851475143))
The dict {5: 2, 1: 4} uses the fact that you don't have to look at all odd numbers. Above 3, all numbers x % 6 == 3 are multiples of 3, so you need to look at only x % 6 == 1 and x % 6 == 5, and you can hop between these by alternately adding 2 and 4, starting from 5.
Use itertools.islice() if your indices are long numbers:
from itertools import islice, count
islice(count(start, step), (stop-start+step-1+2*(step<0))//step)
Python 3's range() can handle python longs as well.
Simplified to your case:
for j in islice(count(1), num - 1):
Although xrange seems to achieve what you want, it can't handle numbers that large. You may need to use this recipe from here
CPython implementation detail: xrange() is intended to be simple and fast. Implementations may impose restrictions to achieve this. The C implementation of Python restricts all arguments to native C longs (“short” Python integers), and also requires that the number of elements fit in a native C long. If a larger range is needed, an alternate version can be crafted using the itertools module:
islice(count(start, step), (stop-start+step-1+2*(step<0))//step).