python - 查找数字的算法

Question

编写一个递归算法，枚举显性素数。您的算法应该在找到它们时(而不是在末尾)打印显性素数。默认情况下，我们将我们正在寻找的显性素数限制为最大值 10^12，预期运行时间应该在一分钟左右或不到一分钟.

以下是我的 python 代码，它没有按预期工作:

import math
def test_prime(n):
    k = 2
    maxk = int(math.sqrt(n))
    while k <= maxk:
        if n % k == 0:
            return False
        if k == 2:
            k += 1
        else:
            k += 2
    return (n is not 1)


def dominant_prime_finder(maxprime=10**12,n=1):
    l = 1    #length of the current number
    while n // 10 > 0:
        l += 1
        n //= 10
    if test_prime(n) == True:
        is_dominant_prime = True
        index_smaller = n
        while l > 1 and index_smaller > 9:
            index_smaller //= 10
            if test_prime(index_smaller) == False:
                is_dominant_prime = False
                break
        for i in range(1,10):
            if test_prime(i*10**l + n) == True:
                is_dominant_prime = False
                break
        if is_dominant_prime == True:
            print(n)
    while n <= maxprime:
        dominant_prime_finder()

Answer 1

您可以在不枚举 10^12 以下的所有数字的情况下解决问题，通过对数字的长度进行递归是低效的。

它的工作方式如下:

• 长度为1的素数是:2,3,5,7。
• 对于所有这些数字，请检查第三个条件，对于任何数字 dn+1∈{1,…,9} ，dn+1dn…d0 都不是质数。对于2没关系。对于 3，它失败了(例如 13)。 将找到的所有素数存储在列表 L 中。对长度为 1 的所有素数执行此操作。
• 在 L 中，您现在拥有所有长度为 2 且首位为素数的素数，因此您拥有所有长度为 2 的主素数候选

在 python 中以递归方式执行此操作可以获得所有显性素数:

def test_prime(n):
    k = 2
    maxk = int(math.sqrt(n))
    while k <= maxk:
        if n % k == 0:
            return False
        if k == 2:
            k += 1
        else:
            k += 2
    return (n is not 1)

def check_add_digit(number,length):
    res = []
    for i in range(1,10):
        if test_prime( i*10**(length) + number ):
            res.append(i*10**(length) + number)
    return res

def one_step(list_prime,length): 
    ## Under 10^12 
    if length > 12:
        return None

    for prime in list_prime: 

        res = check_add_digit(prime,length)

        if len(res) == 0:
            #We have a dominant prime stop 
            print(prime)
        else:
            #We do not have a dominant prime but a list of candidates for length +1
            one_step(res,length+1)

one_step([2,3,5,7], length=1)

这在我的机器上不到一分钟就可以完成。