Как написать рекурсивную функцию для палиндромных простых чисел?

Question

Я пытаюсь написать программу Python, которая использует рекурсивную функцию для поиска палиндромных простых чисел между двумя целыми числами, входящими в качестве входных данных. Пример палиндромного штриха: 313

Я уже знаю, как написать рекурсивную функцию для палиндромов, но я много борюсь с этим. Буду признателен за любую помощь. Thanks

Answer 1

рекурсивная функция для палиндромов

Предположительно сделать проверку палиндром рекурсивно проверять внешние символы:

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 2

Вместо рекурсивного решения, как насчет использования более эффективного набора разрезов?

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 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 

вы можете просто позвонить проверку, когда вы узнаете, если ваш номер палиндром (литье это ул первой). Недостающая часть генерирует комбинацию двух целых чисел, которые вы можете получить, но хорошо, это просто.

Надеюсь, это поможет.

-Edit: Добавление рекурсивной функции для получения простых чисел:

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] 

You может, конечно, также использовать тест primality (2**n-1)%n == 1 в вашей собственной рекурсивной функции палиндрома, которую вы уже имеете.

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

Answer 5

Это решение использует Sieve of Eratosthenes найти простые числа меньше п. Затем он использует базовую проверку палиндрома, какие из этих простых чисел являются палиндромами. Проверка не позволяет преобразовать int s в str с, что требует много времени.

#!/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() 

Если у вас есть вопросы по поводу того, как работает этот код, не стесняйтесь спрашивать меня, комментируя мой ответ. Удачи!