跟踪可删除素数的递归函数-Python 3 [英] Recursive Function For Tracing Deletable Primes - Python 3

问题描述

可删除素数是素数，它可以按一定顺序删除其数字以始终创建素数，并最终以一位数素数结尾.例如，3301 是一个可删除的素数，因为它可以像这样操作:3301 ->331->31->3 .我正在尝试用Python编写一个递归函数，该函数将可删除质数的所有路径追溯到其个位数的根，但是我完全陷入了困境.它已经超越了我的头脑，我什至不能再遵循自己的代码了.函数所需输出的完整示例是 getTraces(3793)返回 [[3793，373，73，7]，[3793，373，73，3]，[3793、373、37、7]，[3793、373、37、3]，[3793、379、79、7]，[3793、379、79、3]，[3793、379、37、7]，[3793，379，37，3]]

A deletable prime is a prime number that can have its digits removed in a certain order to always create primes, and eventually end up with a single digit prime. For example, 3301 is a deletable prime because it can be manipulated like this: 3301 -> 331 -> 31 -> 3. I'm trying to write a recursive function in Python that traces the all paths of a deletable prime back to its single digit root(s) but I'm completely stuck. It has gotten way over my head and I can't even follow my own code anymore. A complete example of the desired output for the function is something along the lines of getTraces(3793) returns [[3793, 373, 73, 7], [3793, 373, 73, 3], [3793, 373, 37, 7], [3793, 373, 37, 3], [3793, 379, 79, 7], [3793, 379, 79, 3], [3793, 379, 37, 7], [3793, 379, 37, 3]]

这是我拥有的函数的当前版本(如果有帮助).我试图让它返回所有可能路径的列表，以一位数为素数，但是我无法绕着递归的思考来使它跟踪所有路径并将它们整齐地放在列表中:

Here is the current version of the function I have (if this of any help). I'm trying to get it to return a list of all the possible paths to a single digit prime but I can't wrap my head around the recursive thinking necessary to have it trace all the paths and put them neatly in a list:

def getTraces(prime):
    paths = []
    print("Parents: " + str(asc(prime)))
    for p in asc(prime):
        if len(str(p)) == 1:
            print("One Digit Prime: "+ str(p))
            return [p]
        else:
            traceArray = getTraces(p)
            print("Trace: " + str(traceArray))
            if traceArray != []:
                for t in traceArray:
                    paths.append(str(prime) + ", " + str(p) + ", " + str(t))
                #traceString = str(p) + ", " + str(traceArray)
    return paths

此函数仅返回一个素数的所有父母的列表(所有可能的素数都删除了一位数字)，并在getTraces()函数中使用

This function just returns a list of all the parents of a prime (all the possible primes with one digit removed) and is used in the getTraces() function

def asc(prime):
    adj = []
    if(isPrime(prime)):
        s = str(prime)
        if len(s) == 1: return []
        for i in range(0, len(s)):
            num = int(s[:i] + s[i+1:])
            if isPrime(num):
                if not num in adj:
                    adj.append(num)
    else:
        print("That is not a prime number!")
        return None
    return adj

这是我制作的一种非常好的实用程序方法，用于检查数字是否为质数:

And a very nice utility method I made for checking if a number is prime:

def isPrime(x):
    if x <= 1: return False
    for i in range(1, int(sqrt(x)) + 1):
        if not gcd(i, x) == 1:
            #print(i)
            return False
    return True

推荐答案

我终于能够解决我的问题，所以我认为我也应该发布我的答案，因为我无法删除问题.由于我想出了一种无需递归的方式来做，所以我最终放弃了递归地进行操作，但是我感谢每个人提供的帮助和指导.这是我的解决方案:

I was finally able to solve my problem so I thought I might as well post my answer since I can't delete the question. I eventually gave up on trying to do it recursively since I came up with a way to do it without recursion, but I appreciate the help and pointers everyone provided. Here is my solution:

def trace(prime):
    def sub(paths):
        result = []
        """Increases path depth by one"""
        for path in paths:
            pathResult = []
            for parentOfLast in asc(path[len(path)-1]):
                pathResult.append(path + [parentOfLast])
            #print("Path: " + str(pathResult))
            result += (pathResult)
        return result
    result = [[prime]]
    while len(result[0]) < len(str(prime)):
        result = sub(result)
    return result

这篇关于跟踪可删除素数的递归函数-Python 3的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！