Как найти простое число с помощью рекурсии в Python

Я должен выяснить, является ли число (N) простым или не использует рекурсию, циклы не допускаются. Я пытался преобразовать обычный код, который использует цикл for, в рекурсивный, но он не ведет себя так же. Эта функция включена в другую функцию, которая является частью другой функции. только параметры a и N должны использоваться и передаваться. Вот моя функция.

a=2
def is_prime(a,N):
prime = True
if N <=1:
    return 
else:
    if a >= N:
        return 
    else:
        if N == 2: 
            prime = True
            print(N)
            return 
        elif (N % a) == 0:
            prime = False
            return is_prime(a+1,N)
        else:
            prime = True
            print(N)

return

Я считаю, что ошибка где-то здесь.

elif (N % a) == 0:
            prime = False
            return is_prime(a+1,N)
        else:
            prime = True
            print(N)

Вот код, который я пытался преобразовать.

if num > 1:
   for i in range(2,num):
      if (num % i) == 0:
         print(num,"is not a prime number")
         print(i,"times",num//i,"is",num)
         break
   else:
      print(num,"is a prime number")

else:
   print(num,"is not a prime number")
Источник

7 ответов

Решение

Ваше решение близко, всего несколько изменений, необходимых для его работы.

def is_prime(a,N):
    print(a, N)
    if N <= 1:
        return 
    else:
        if a >= N:
            print(N)
        else:
            if N == 2: 
                print(N)
            elif (N % a) == 0:
                return False
            else:
                return is_prime(a+1,N)

    return False

Вы не приводили примеров вызова этой функции, но я предполагаю, что она всегда вызывается с a будучи 2, так как любое другое значение не имеет смысла. Так что, если вы запустите вышеуказанную функцию следующим образом, вы должны получить правильный вывод:

print(is_prime(2, 7))  => True
print(is_prime(2, 4))  => False
print(is_prime(2, 37)) => True

Я думаю, у вас есть неправильное понимание того, как работает рекурсия, вы назначаете это prime переменная в теле функции, но никогда ничего с ней не делает. Может быть, ваше замешательство происходит из-за неправильного понимания областей применения в Python. Тот prime переменная не будет разделена между вызовами, она просто создаст новую prime каждый раз.

РЕДАКТИРОВАТЬ: не понимал, что вы хотели, чтобы функция просто распечатать простое число, если оно простое, изменил код соответствующим образом.

Источник 
def prime(n,j):
    if(n<2):
        return False
    if(j==n):
        return True
    if(n%j==0):
        return False
    return prime(n,j+1)

print(prime(n,2))

Число называется простым, если оно делится только на себя и на 1. Поэтому итерация от 2 до n-1, если n делится на любое из (2,3,4,..n-1), возвращает False.
Если j == n тогда нет такого числа из (2,3,4...n-1), делимого на n, следовательно, оно простое.

Источник

Ваша функция иногда возвращает что-то, а иногда ничего не возвращает - это должно быть либо одно, либо другое, а не оба. В этом случае is_prime() выглядит как логическая функция, поэтому она должна возвращать True или False. Мы оставим печать вызывающей стороне:

def is_prime(N, a=3):

    if N == 2:  # special case
        prime = True
    elif N <= 1 or N % 2 == 0:  # too small or even
        prime = False
    elif a * a > N:  # tried all divisors to sqrt, must be prime
        prime = True
    elif (N % a) == 0:  # divides evenly, not a prime
        prime = False
    else:  # can't tell yet, recursively try the next (odd) divisor
        prime = is_prime(N, a+2)

    return prime

for x in range(100):
    if is_prime(x):
        print(x)

Будь проще. Продумайте каждый возможный случай. Избегайте ненужного увеличения глубины отступа, это усложняет ваш код.

Вышеупомянутое решение пытается ускорить обнаружение простых чисел, избегая четных чисел (как делителей, так и чисел) и ограничивая делитель квадратным корнем числа. Это может иметь значение, так как без этих оптимизаций рекурсивное решение, вероятно, исчерпает пространство стека вызовов на уровне N=1000, тогда как вышеупомянутое должно перейти к N=1 000 000 без расширения стека вызовов.

Источник

Поскольку было так много интересных попыток улучшить код, я попробовал, и вот мое лучшее решение для любого случая определения того, является ли число простым с помощью рекурсии. Вам придется добавить операторы печати или любую другую логику самостоятельно, но основная идея довольно проста:

      def is_prime_recursive(n, checkpoint = 2):
if n in [1, checkpoint]:
    return True
if n % checkpoint == 0:
    return False
return is_prime_recursive(n, checkpoint + 1)
  • Функцию следует вызывать только с одним параметром — числом для проверки — , так как оно устанавливает число два в качестве первой контрольной точки;
  • Если число равно единице или текущей контрольной точке (в первом случае единице или двум), то это простое число;
  • Если число делится на текущую контрольную точку, вернуть false, потому что это не простое число;
  • Если число не попадает ни в один из предыдущих случаев, вызовите функцию еще раз, но на этот раз увеличьте контрольную точку на единицу;

Это повторяется до тех пор, пока число не попадет в один из случаев — в худшем случае число является простым: первый случай (n == контрольная точка)

Источник

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

if a >= N:
    print(N)
    return

Далее нам нужно разобраться со всеми случаями, когда N > 1:

if N == 2: 
    prime = True
    print(N)
    return 
elif (N % a) == 0:
    prime = False
    return is_prime(a+1,N)
else:
    prime = True
    print(N)

Первая проверка, if N == 2 не нужен, так как до этого уже есть блок, который обрабатывает все случаи, когда N прост, поэтому он может быть удален. Тем не менее, наличие там не причинит никакого вреда.

Следующий блок, который проверяет, если N делится на a следует прекратить рекурсию. Так как вы знаете, что N не просто, вы должны просто остановиться на этом.

Последний блок, который выполняется, когда N не делится на a следует сделать рекурсию вместо. В настоящее время рекурсия прекращается, как только N % a != 0 что явно неправильно.

Вот рабочий пример с вышеуказанными модификациями и очисткой:

def is_prime(N, a=2):
    if N <= 1:
        return
    elif a >= N:
        print(N)
    elif N % a != 0:
        is_prime(N, a + 1)
Источник

Для печати списка простых чисел между заданным диапазоном

l=[]
def primenum(x,y):
    global l
    if x==y:
        print(l)
    else:
        m=0
        for i in range(1,x+1):   
            if x%i==0:
                m+=1
        if m==2 or x==1:
            l+=[x,]
            return primenum(x+1,y)
        else:
            primenum(x+1,y)
Источник 
def is_prime(n):
  def prime_helper(n, x):
    if n == 1:
      return False
    elif n % x == 0:
      return False
    else:
      return prime_helper(n , x+1) if x * x <= n else True 
  return prime_helper(n, 2)

если вы не хотите использовать вспомогательную функцию

def is_prime(n, x=2):
    if n == 1:
      return False
    elif n % x == 0:
      return False
    else:
      return is_prime(n , x+1) if x * x <= n else True

Кроме того, вам не нужно проверять все числа между (1 - N), а только до sqrt(n). Вы можете изменить свой итеративный подход к

для цикла

from math import sqrt 
def is_prime(n):
  if n == 1:
     return False
  for i in range(2, round(sqrt(n)) + 1):
     if n % i == 0:
        return False
  return True

пока цикл

def is_prime(n):
  if n == 1:
    return False
  i = 2
  while i * i <= n:
     if n % i == 0:
        return False
     i += 1
  return True
Источник
Другие вопросы по тегам