python - 在 python 中处理任意大的数字

Question

我正在通过 Euler 项目工作，以进一步提高我的编程技能。在重新访问问题 3 的代码后，我遇到了一个有趣的问题。这是我的代码:

# prime numbers are only divisible by unity and themselves
# (1 is not considered a prime number by convention)
def isprime(n):
    '''check if integer n is a prime'''
    # make sure n is a positive integer
    n = abs(int(n))
    # 0 and 1 are not primes
    if n < 2:
        return False
    # 2 is the only even prime number
    if n == 2: 
        return True    
    # all other even numbers are not primes
    if not n & 1: 
        return False
    # range starts with 3 and only needs to go up the squareroot of n
    # for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True


try:
    num = int(input('Please input a natural number:'))
except ValueError:
    print("Erm.. No. I need a number.")


mylist = []
check = True
newnum = num
i= 0


if isprime(num):
    print("%r is a prime number."%num)

else:
    while check:
        if isprime(i):
            if newnum % i ==0:
                mylist.append(i)
                print("%r is a prime factor of %r"%(i,num))
                newnum = newnum/i
                i=0

                if newnum ==1:
                    check = False

        if i==num:
            print("I guess the program broke.")
            check = False
        i+=1

    print ("The largest prime factor for %r is:"%num)
    print (max(mylist))
    print ("The list of prime factors for %r is:"%num)
    print (mylist)

所以我遇到的问题是这段代码将永远运行超过 17 位的数字(我怀疑任何高于 144155188075855872 的数字是 2^59；它适用于一些 18 位数字而不是其他数字)。

我发现，如果我输入一个比这个大的数字，然后用 Windows 计算器检查答案，答案会非常接近整数，但会有小数部分。

如何更改我的函数以接受并正确计算任意大的数字？ (最好不使用非标准库)

谢谢!

Answer 1

Python 整数是任意精度的。我在您的代码中看到的唯一可能无法高精度运行的是这种浮点计算:

int(n**0.5)+1

由于 float 是近似值，对于大于 64 位 float 可以精确表示的数字(大约 2 到 50 左右)，您将得到舍入误差。相反，使用整数计算:

for x in itertools.count(3, 2):
    if x > n ** 2:
        break
    if n % x == 0:
        return False