python - 求最大素数 "within"一个数

Question

对于这道题，我需要在一个较大的数中找出最大的质数。出于示例的目的，假设较大的数字是“123456789”，那么我必须检查的一些数字是 12、456、234567 等。

我写了一些 Python 代码来解决这个问题，但是对于我要检查的数字来说它运行得非常慢。我实际使用的数字大约是 10000 位数字，因此我需要查看很多数字。这是我的代码:

num = "123456789"

def isPrime(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, long(n**0.5)+1, 2):
    if n % x == 0:
        return False
return True

def largestPrime():
    largest = 2
    for i in range(0,len(num)):
        for j in range(i+1,len(num)):
            if isPrime(long(num[i:j])):
                if long(num[i:j]) > largest:
                    largest =long(num[i:j])
    print largest

def main():
    largestPrime()

main()

我很确定这段代码给出了正确的答案，但正如我所说，它真的很慢。谁能帮我弄清楚如何加快速度？

感谢您的帮助!

Answer 1

我可能会使用从总位数开始并查看它是否为素数的策略。然后继续将数字减一位，同时向左移动以查看它是否为质数。让我用一个例子来解释:

123456789

First check the 9-digit number: 123456789
Then check the 8-digit numbers: 23456789, 12345678
Then Check the 7-digit numbers: 3456789, 2345678, 1234567
etc.