(в25) Обработка целых чисел. Делимость

Поиск делителей числа

Проверка делимости числа a на число b:

if n % d == 0:
      print("Делится")
else: print("Не делится")

Для нахождения всех делителей числа n выполним перебор всех чисел от 1 до n и для каждого будем делать проверку делимости, и если число является делителем, будем добавлять его в список. 

Замечание 1. Перебор всех чисел от 1 до n будет долгим, если число n велико. Поэтому, будем беребор делать до значения \(\sqrt{n}\). Остальные делители будем вычислять через найденный делитель (d) как n//d.

Замечание 2. На самом деле, делители удобнее добавлять в такую структуру данных как множетсво (set()). Это позволит избавиться от двойных делителей в том случае, если число является квадртатом другого числа. 

 

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

Простое число — натуральное число, имеющее ровно два различных натуральных делителя. Другими словами, натуральное число p является простым, если оно отлично от 1 и делится без остатка только на 1 и на само p.

Для проверки числа на простоту, напишем функцию, которая будет возвращать True, если число простое и False в противном случае. Функция будет перебирать все числа от 2 до n-1 и проверять делится ли на него наше число n. Если делится, то функция будет завершать свою работу и возвращать значение True. По окончании перебора, если мы не нашли ни одного числа, являющегося делителем, функция вернет True. Также необходимо сделать проверку на равенство одному и вернуть False, если n<=1.