Проверка простоты числа перебором делителей
Простые числа — это натуральные числа больше единицы, которые делятся нацело только на единицу и на себя. Например, число 3 простое, так как нацело делится только на 1 и 3. Число 4 сложное, так как нацело делится не только на 1 и 4, но также на число 2.
Алгоритм перебора делителей заключается в последовательном делении заданного натурального числа на все целые числа, начиная с двойки и заканчивая значением меньшим или равным квадратному корню из тестируемого числа. Таким образом, в данном алгоритме используется цикл, счетчик итераций которого последовательно принимает значения ряда натуральных чисел от 2 до корня из исследуемого числа.
Перебор делителей применяется в том числе для определения, является ли натуральное число простым, или оно является сложным, то есть составным. Касаемо данной задачи, если хотя бы один делитель делит исследуемое число без остатка, то оно является составным. Если ни одного такого делителя не находится, то число признается простым.
from math import sqrt n = int(input()) prime = True i = 2 while i sqrt(n): if n % i == 0: prime = False break i += 1 if prime: print("Простое число") else: print("Составное число")
В программе мы сначала предполагаем, что введенное число n является простым, и поэтому присваиваем переменной prime значение True . Далее в цикле перебираются делители (переменная i ) от 2-х до квадратного корня из числа n . Как только встречается первый делитель, на который n делится без остатка, меняем значение prime на False и прерываем работу цикла, так как дальнейшее тестирование числа на простоту смысла не имеет.
Если после выполнения цикла prime осталась истиной, сработает ветка if условного оператора. В случае False , поток выполнения заходит в ветку else .
Если знать о такой особенности циклов в Python как возможность иметь ветку else , то код можно упростить, избавившись от переменной prime и ее проверки условным оператором после завершения работы цикла.
from math import sqrt n = int(input()) i = 2 while i sqrt(n): if n % i == 0: print("Составное число") break i += 1 else: print("Простое число")
Ветка else при циклах (как while , так и for ) срабатывает, если в основном теле цикла не происходило прерывания с помощью break . Если break сработал, то тело else выполняться не будет. При использовании таких конструкций также следует помнить, что если условие в заголовке цикла сразу возвращает ложь (то есть тело цикла не должно выполняться ни разу), код тела else все-равно будет выполнен.
Программы выше будут определять числа 0 и 1 как простые. Это неправильно. Данные числа не являются ни простыми, ни сложными. Для проверки ввода пользователя, можно воспользоваться условным оператором или зациклить запрос числа, пока не будет введено корректное значение:
n = 0 while n 2: n = int(input())
Рассмотрим функцию, которая определяет, является ли число простым:
from math import sqrt def is_prime(n): i = 2 while i sqrt(n): if n % i == 0: return False i += 1 if n > 1: return True a = int(input()) if is_prime(a): print("Простое число") else: print("Число НЕ является простым")
Здесь нет необходимости в прерывании работы цикла с помощью break , так как оператор return выполняет выход из тела всей функции.
Если цикл полностью отработал, выполнится выражение return True , находящееся ниже цикла. Оно помещено в тело условного оператора, чтобы исключить возврат «истины», когда в функцию передаются числа 0 или 1. В этом случае функция вернет объект None .
Программа не защищена от ввода отрицательного числа. При этом будет генерироваться ошибка на этапе извлечения квадратного корня.
Нарисуем блок-схему тестирования числа на простоту (без дополнительных проверок и оператора break ):
from math import sqrt n = int(input()) prime = True i = 2 while i sqrt(n) and prime is True: if n % i == 0: prime = False i += 1 if prime: print("Простое число") else: print("Составное число")
—>
X Скрыть Наверх
Решение задач на Python
Вывести все простые числа в диапазоне от a до b
Справка:
Простое число — это натуральное число, больше единицы, имеющее ровно два натуральных делителя: 1 и само себя.
Пример последовательности простых чисел:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, бесконечно. Задача:
Напишите программу, которая вводит натуральные числа a и b и выводит все простые числа в диапазоне от a до b. Входные данные:
Входная строка содержит два натуральных числа, a и b . Гарантируется, что a ≤ b . Выходные данные:
Программа должна вывести в одной строке через пробел все простые числа на отрезке [ a , b ] . Если таких чисел нет, программа должна вывести 0. Примеры:
входные данные:
20 30
выходные данные:
23 29 входные данные:
24 28
выходные данные:
0 Решение:
a , b = map ( int , input ( ) . split ( ) )
ls = [ ]
for i in range ( a , b + 1 ) :
if all ( i % n != 0 for n in range ( 2 , i ) ) :
ls. append ( str ( i ) )
if len ( ls ) :
print ( ‘ ‘ . join ( ls ) )
else :
print ( 0 )
Раздел: Обучение Метки: Python, Легко, Примеры
- Здоровое питание панды По 15.04.2020
- Подсчитать сумму только положительных чисел 13.04.2020
- Минутка генетики 04.05.2019
- Простенький бэкап программ хранящих данные в файлах 03.05.2019
- Найти среднее арифметическое 2-х средних элементов массива 27.03.2019
- КАК КАКАТЬ к записи Вывести все простые числа в диапазоне от a до b
- КАК КАКАТЬ к записи Вывести все простые числа в диапазоне от a до b
- Нсгп7н к записи Подсчитать сумму только положительных чисел
- lourdes к записи Здоровое питание панды По
- laurie к записи Здоровое питание панды По
Вывести все простые числа в диапазоне Python – пошаговый алгоритм
Простое число — это натуральное число, которое больше 1 и не имеет положительного делителя, кроме 1 и самого себя, например 2, 3, 5, 7, 11, 13 и так далее.
Пользователю даются два целых числа, нижнее значение и верхнее значение. Задача состоит в том, чтобы написать программу Python для вывода всех простых чисел в заданном интервале (или диапазоне).
Чтобы напечатать все простые числа в заданном интервале, пользователь должен выполнить следующие шаги:
- Шаг 1: Переберите все элементы в заданном диапазоне.
- Шаг 2: Проверьте для каждого числа, есть ли у него какой-либо множитель между 1 и самим собой.
- Шаг 3: Если да, то число не простое, и оно перейдет к следующему числу.
- Шаг 4: Если нет, то это простое число, и программа распечатает его и проверит следующее число.
- Шаг 5: Цикл прервется, когда будет достигнуто верхнее значение.
Пример: код Python для печати простого числа в заданном интервале.
# First, we will take the input: lower_value = int(input("Please, Enter the Lowest Range Value: ")) upper_value = int(input("Please, Enter the Upper Range Value: ")) print("The Prime Numbers in the range are: ") for number in range(lower_value, upper_value + 1): if number > 1: for i in range(2, number): if(number % i) == 0: break else: print(number)
Please, Enter the Lowest Range Value: 14 Please, Enter the Upper Range Value: 97 The Prime Numbers in the range are: 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Заключение
В этом уроке мы показали, как написать код для печати простых чисел в заданном диапазоне чисел.
Алгоритм нахождения простых чисел
Дело было давно, в университете, когда мы начали изучать язык программирования Pascal и домашним заданием стало создание алгоритма нахождения простых чисел.
Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.
Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.
# Листинг 1 # вводим N n = input(«n python»># Листинг 2 n = input(«n python»># Листинг 3 n = input(«n python»># Листинг 4 from math import sqrt n = input(«n python»># Листинг 5 from math import sqrt n = input(«n python»># Листинг 6 from math import sqrt n = input(«n python»># Листинг 7 n = input(«n python»># Листинг 8 n = input(«n tm-article-presenter__meta»>