4

我正在通过项目 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 计算器检查答案，答案将非常接近整数，但它会有小数部分。

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

谢谢！

4

1 回答 1

6

Python 整数是任意精度的。我在您的代码中看到的唯一可能无法在高精度下工作的是这个浮点计算：

int(n**0.5)+1

由于浮点数是近似值，因此对于大于 64 位浮点数可以精确表示的数字（发生在 2 到 50 左右），您将得到舍入误差。相反，使用整数计算：

for x in itertools.count(3, 2):
    if x > n ** 2:
        break
    if n % x == 0:
        return False
于 2013-10-25T20:09:45.963 回答