范围太大Python

Question

我试图找到数字x的最大素数因子,Python给出了范围太大的错误.我尝试过使用x range但是我得到一个OverflowError:Python int太大而无法转换为C long

x = 600851475143
maxPrime = 0


for i in range(x):
    isItPrime = True
    if (x%i == 0):
        for prime in range(2,i-1):
            if (i%prime == 0):
                isItPrime = False
        if (isItPrime == True):

            if (i > maxPrime):
                maxPrime = i;

print maxPrime

Answer 1

在旧的(2.x)版本的Python中,xrange只能处理Python 2.x ints,它们受到平台的本机长整数大小的约束.此外,range事先在Python 2.x上分配一个包含所有数字的列表,因此不适用于大型参数.

您可以切换到3.x(推荐),或者long int(C)为64位长的平台,或者使用以下插件:

import itertools
range = lambda stop: iter(itertools.count().next, stop)

同样地,以简单的形式:

def range(stop):
   i = 0
   while i < stop:
       yield i
       i += 1

Answer 2

这就是我要做的:

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]

这很快,我认为是对的.采取所发现因素的最大值非常简单.

2017年11月8日

回到这5年后,我会使用yield并yield from加上更快的计数超过素数范围:

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

dict {5: 2, 1: 4}使用的事实是你不必查看所有奇数.以上3个,所有的数字x % 6 == 3是3的倍数,所以你需要看只有x % 6 == 1和x % 6 == 5,并且可以通过交替增加2和4,5起它们之间跳跃.