python是否显示大整数的问题？

Question

我有一个代码来计算最高素数因子600851475143.

def PRIME(a):                #Check if no is prime
    f = 0
    i = 2
    while(i < a/2):          #No factor of a no can be greater than a/2
        if (a % i == 0):
            f = 1
            break
        i = i + 1

    if(f == 1):
        return 0
    else:
        return 1


def PFIND(a):
    for i in range(1, 100000):   #Iteratively check if the no is prime
        if PRIME(a/2 - i):       #No factor of a no can be greater than a/2.
            if (a % (a/2 - i) == 0):
                return (a/2 - i)
print PFIND(600851475143)

但是代码会一直运行,并且不会给出任何输出.

Answer 1

Python对大整数的支持很好.我认为你的问题是,你正在为蛮力发现因素和测试你的因素是否为素数做非常慢的算法.如果你只是颠倒这两个测试的顺序(即,测试它是否是一个因素,然后测试它是否是素数),它会更快.

但也许问题在于使用更复杂的算法.也许你应该使用Rabin-Miller测试而不是蛮力.