Простые числа рекурсия python

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

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

a=2 def is_prime(a,N): prime = True if N = 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 = 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 каждый раз.

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

Число называется простым, если оно делится только на себя и на 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 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 == контрольная точка)

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

Далее нам нужно разобраться со всеми случаями, когда 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 = N: print(N) elif N % a != 0: is_prime(N, a + 1) 

Источник

Проверка числа на простоту с использованием рекурсии

Программа получает на вход число и определяет, является ли это число простым или нет, используя рекурсивный алгоритм.

Решение задачи

1. Принимаем число и записываем его в отдельную переменную.
2. Передаем это число в качестве аргумента в рекурсивную функцию. В качестве второго аргумента этой рекурсивной функции будет переменная-делитель. Она при первом вызове инициируется значением None .
3. Затем делителю присваивается значение на единицу меньшее, чем наше число, и проверяется, делится ли число на него без остатка. Если делится, программа завершает работу и определяет, что число не является простым.
4. Если нет, то функция рекурсивно вызывает саму себя, причем второй аргумент (делитель) теперь на 1 меньше, чем был до этого.
5. Таким образом, мы проверяем делимость исходного числа на все числа, которые меньше него и больше 1 . Если хоть на одно из этих чисел оно делится без остатка, функция возвращает False . В противном случае число считается простым.
6. Выводим результат на экран.
7. Конец.

Исходный код

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

def check(n, div = None): if div is None: div = n - 1 while div >= 2: if n % div == 0: print("Число не является простым") return False else: return check(n, div-1) else: print("Число является простым") return True n = int(input("Введите число: ")) check(n)

Объяснение работы программы

1. Принимаем число и записываем его в отдельную переменную n .
2. Передаем это число в качестве аргумента в рекурсивную функцию check() . В качестве второго аргумента этой рекурсивной функции передается переменная div , которая будет делителем. Она при первом вызове инициируется значением None .
3. Затем делителю присваивается значение на единицу меньшее, чем наше число, и проверяется, делится ли число на этот делитель без остатка. Если делится, программа завершает работу и определяет, что число не является простым.
4. Если нет, то функция рекурсивно вызывает саму себя следующим образом: check(n, div-1) . Заметьте, что второй аргумент div теперь на 1 меньше, чем был до этого.
5. Таким образом мы проверяем делимость исходного числа на все числа, которые меньше него и больше 1 . Если хоть на одно из этих чисел оно делится без остатка, функция возвращает False : число не является простым. А если нет, то число простое.
6. Выводим результат на экран.

Результаты работы программы

Пример 1: Введите число: 13 Число является простым Пример 2: Введите число: 30 Число не является простым

Примечание переводчика

Данный код приведен лишь для примера использования рекурсии. С вычислительной точки зрения он является крайне несовершенным. Так, например, рассматриваемый нами ранее алгоритм решета Эратосфена гораздо экономичней. В данном же коде есть недостатки. Например, совсем необязательно проверять, делится ли число n на n — 1 без остатка, и так ясно, что нет. Предоставим читателям возможность самим улучшить данный код.

Источник

Рекурсия. Определить, является ли натуральное число простым

Напишите рекурсивную программу, которая определяет, является ли переданное ей натуральное число простым.
Программа должна вывести слово ‘YES’, если переданное ей число – простое, и слово ‘NO’ в противном случае.

Вот код, который мне удалось написать.
На тестирующей системе из 22 тестов 5 не проходят.
В чём дело — не пойму.

Пожалуйста, посмотрите код, есть, наверное, ошибки, или просто что-то не так:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

def prostoe (d) : # d - делитель числа N if d > last_d : return 0 if N % d == 0 : return 1 else : return prostoe (d + 1) N = int (input ()) last_d = int (N ** 0.5) # делители, равные 1 и N не проверяем d = 2 if N == 1 : print ('NO') elif prostoe (d) == 0 : print ('YES') else : print ('NO')

Определить, является ли число простым
Напишите логическую функцию logi(x), определяющую, является ли заданное натуральное число x.

Определить является ли число простым
2) Написать функцию, определяющую, является ли число простым.

Определить является ли число простым
выдает ошибку в строке if def prost(n): d = 2 while n % d != 0: d += 1 print(d.

Определить, является ли число простым
import math n=int(input()) f=True for i in range(2, round(math.sqrt(n))+1): if (n%i==0): .

Дано натуральное число. Выяснить, является ли оно простым. Инструкцию цикла с параметром не использовать
Дано натуральное число. Выяснить, является ли оно простым. Инструкцию цикла с параметром не.

def isPrime(num, ans = 2): if num  ans*ans: return True if num % ans == 0: return False return isPrime(num, ans + 1)

Определить является ли заданное число простым
Составьте программу, который выдает 1, если заданное число простое и 0 – в противном случае. Число.

Рекурсия: определить, является ли заданное натуральное число простым
Написать рекурсивную функцию, определяющую, является ли заданное натуральное число простым. .

Рекурсия: определить, является ли заданное натуральное число простым
1. Написать функцию определения, является ли заданное натуральное число простым.

Рекурсия: определить, является ли заданное натуральное число простым
Написать функцию определения, является ли заданное натуральное число простым. (рекурсивно)

Рекурсия. Определить, является ли заданное натуральное число простым.
Определить, является ли заданное натуральное число простым. Решите пожалуйста, в долгу не.

Источник

Проверка числа на простоту

Программа принимает на вход число и проверяет, простое оно или нет.

Решение задачи

1. Принимаем на вход число и записываем его в отдельную переменную.
2. Инициализируем переменную, которая будет выполнять роль счетчика, значением 0 .
3. Организуем цикл for в диапазоне от 2 до значения проверяемого числа, деленного на 2 (речь идет, конечно, о целочисленном делении).
4. Затем находим количество делителей нашего числа. При помощи условного оператора if мы проверяем, делится ли число без остатка, и затем, если делится, увеличиваем наш счетчик на единицу.
5. Если число делителей равно 0 , то проверяемое число является простым.
6. Выводим результат на экран.
7. Конец.

Исходный код

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

a = int(input("Введите число: ")) k = 0 for i in range(2, a // 2+1): if (a % i == 0): k = k+1 if (k 
Объяснение работы программы

  
Пользователь вводит число, и оно сохраняется в переменную a .
  
Инициализируем переменную k значением 0 . Эта переменная будет выполнять роль счетчика.
  
Запускаем цикл for в диапазоне от 2 до значения проверяемого числа, деленного на 2 (речь идет, конечно, о целочисленном делении). Напоминаем, что само число и 1 делителями мы считать не будем.
  
Затем, при помощи инструкции if , на каждой итерации цикла мы проверяем, делится ли наше число без остатка на числа из выбранного диапазона цикла. Если делится, то переменная k , выполняющая роль счетчика, увеличивается на единицу.
  
Если число делителей равно 0 , то проверяемое число является простым.
  
Выводим полученный результат на экран.

Результаты работы программы
Пример 1: Введите число: 7 Число простое Пример 2: Введите число: 35 Число не является простым
 
Еще более 50 задач на числа в нашем телеграм канале Python Turbo. Уютное сообщество Python разработчиков.
 
Источник