如何编写回文素数的递归函数？

Question

我一直在尝试编写一个 Python 程序，该程序使用递归函数来查找作为输入提供的两个整数之间的回文素数。回文素数示例：313

我已经知道如何为回文写递归函数，但我在这方面苦苦挣扎。我将不胜感激任何帮助。谢谢

Answer 1

不使用递归解决方案，使用更有效的列表切片怎么样？

def isPalindrome(number):
    nstr = str(number)
    return nstr == nstr[::-1]

这通过将数字转换为字符串并比较它的反向对应项来实现。也有确定回文的已知算法，使用全局变量：

sum = 0


def is_palindrome(number):
    return palindrome_sum(number) == number


def palindrome_sum(number):
    global sum
    if number != 0:
        remainder = number % 10
        sum = sum * 10 + remainder
        palindrome_sum(number / 10) * 10 + remainder

    return sum

对于没有全局变量的数学递归函数，可以使用这个算法：

import math

def is_palindrome(number):
    return palindrome_sum(number) == number


def palindrome_sum(number, sum=0):
    iters = 0
    if number != 0:
        iters = int(math.log10(number))
        remainder = number % 10
        sum = palindrome_sum(number / 10) + remainder * 10 ** iters

    return sum

它使用数字的长度来查找它在结果数字中的位置。长度可以通过int(math.log10(number))来计算。

Answer 2

recursive function for palindromes

大概是为了递归地进行回文检查，你检查了外部字符：

def is_pali(s):
    if len(s) <= 1:
        return True
    else:
        return s[0] == s[-1] and is_pali(s[1:-1])

现在您可以遍历数字并查看哪些是回文：

[i for i in range(n, m) if is_pali(str(i))]

Answer 3

可能你已经经历过这个想法，但这是我会做的......

如果你有这样的回文函数:

def palindrome(word):
if len(word) == 1 or (len(word) == 2 and word[0] == word[1]):
    return True
else:
    if word[0] == word[len(word)-1]:
        return palindrome(word[1] + word[len(word)-2])
    else:
        return False

假设你有一个函数可以判断一个数是否为质数（这是我从 here 中得到的）：

def is_prime(number):
if number > 1:
    if number == 2:
        return True
    if number % 2 == 0:
        return False
    for current in range(3, int(math.sqrt(number) + 1), 2):
        if number % current == 0: 
            return False
    return True
return False

当你发现你的数字是否是回文时，你可以调用验证（首先将它转换为 str ）。缺少的部分是生成您可能会得到的两个整数的组合，但这很简单。

希望这对您有所帮助。

-编辑：添加递归函数以获取素数：

def prime(number,limit = 1):
if limit == number:
    return True
else:
    if number % limit == 0 and limit != 1:
        return False
    else:
        return prime(number, limit + 1)

Answer 4

因为 30000 是限制，所以这个有效（101101 是它出错的最小数字）：

>>> [n for n in range(2, 500) if str(n) == str(n)[::-1] and (2**n-1)%n == 1]
[2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383]

您当然也可以在自己已有的递归回文函数中使用 (2**n-1)%n == 1 素数测试。

http://en.wikipedia.org/wiki/Fermat_primality_test

Answer 5

此解决方案使用 Sieve of Eratosthenes 查找小于 n 的素数。然后它使用基本的回文检查这些质数中哪些是回文。该检查避免了将 ints 转换为 strs，这是一项耗时的操作。

#!/usr/bin/env python2.7

def primeslt(n):
    """Finds all primes less than n"""

    if n < 3:
        return []

    A = [True] * n
    A[0], A[1] = False, False

    for i in range(2, int(n**0.5)+1):
        if A[i]:
            j = i**2
            while j < n:
                A[j] = False
                j += i

    return (num for num in xrange(n) if A[num])

def is_palindrome(n):
    digits = []
    while n > 0:
        digits.append(n%10)
        n /= 10
    return digits == digits[::-1]

def main():
    while True:
        try:
            i = int(raw_input("Palindromic primes less than... "))
            break
        except ValueError:
            print "Input must be an integer."

    print filter(is_palindrome, primeslt(i))

if __name__ == '__main__':
    main()

如果您对这段代码的工作原理有任何疑问，请随时通过评论我的回答来问我。祝你好运！

如何编写回文素数的递归函数？

How to write a recursive function for palindromic primes?

python

recursion

palindrome