python - 给出一个大数字作为参数后，函数不会返回任何内容

Question

我正在通过做Project Euler来学习Python问题，我被困在 Problem #3 .

我想我已经找到了一个可行的解决方案，但是当插入大数字 600851475143 时，它只是不返回任何内容。我相信它只是加载和加载，因为即使使用 6008514，也需要 10 秒才能返回答案。

# What is the largest prime factor of the number x?
import math

def isPrime(x):
    try:
        sqr = math.sqrt(x)
        if x == 0 or x == 1:
            return 0

        for n in range (2 , int(sqr)+1):
            if x % n == 0:
                return 0
        return 1
    except:
        return 'Give positive numbers.'

def largestPrimeFactor(x):
    if isPrime(x) == 1:
        return 'This number is prime.'
    else:
        largest = -1
        mid = x/2
        for n in range(2,int(mid)+1):
            if isPrime(n):
                if x % n == 0:
                    largest = n

        if largest == -1:
            return 'Enter numbers above 1.'
        else:            
            return largest

print(largestPrimeFactor(600851475143))

Answer 1

这段代码应该可以工作:

    import math

    def isPrime(x):
        try:
            sqr = math.sqrt(x)
            if x == 0 or x == 1:
                return 0
            n = 2
            highest = x
            while n < highest:
                if x%n ==0:
                    return 0
                highest = x/ n
                n +=1
            return 1
        except:
            return 'Give positive numbers.'

    def largestPrimeFactor(x):
        if isPrime(x) == 1:
            return 'This number is prime.'
        n = 2
        highest = x
        largest = 1
        while n < highest:
            if x%n == 0:
                if isPrime(n):
                    largest = n
            highest = x/n
            n +=1
        return largest


    print(largestPrimeFactor(600851475143))

我做了一个优化: 您检查是否每个数字都是 x 的因数，而如果例如 2 不是 x 的因数，则确定 x 的最大因数可以是 x/2。因此，如果 n 不是 x 的因子，则 x 的最大可能因子只能是 x/n。