Делители и простые числа
Делители числа идут парами d и n / d, поэтому их ищут перебором только до квадратного корня из числа. Наименьший делитель, больший единицы, всегда простой, а наибольший делитель, меньший самого числа, получается делением на него. Простоту проверяют тем же перебором, разложение на множители — делением в цикле, а все простые числа диапазона даёт решето Эратосфена.
Как искать делители
Число — делитель числа , если делится на без остатка: n % d == 0.
- Делители идут парами и , меньший из пары не больше . Перебирайте от 1, пока
d * d <= n, и берите оба делителя пары. - Наименьший делитель больше 1 — первый от 2, на который делится. Наибольший делитель меньше равен .
- Число простое, если и ни одно от 2 до его не делит.
- Разложение на простые множители: делите на , пока делится, затем увеличивайте . Остаток больше 1 — последний простой множитель.
- Перебор чисел: цикл
whileсо счётчиком найденных чисел, остановка после нужного количества.
Делители парами: перебор до корня
Делитель натурального числа — натуральное число , на которое делится без остатка. В Python это условие n % d == 0. У каждого есть делители 1 и .
Если — делитель, то тоже делитель: . В каждой паре меньший делитель не больше , иначе произведение пары было бы больше . Поэтому делители перебирают только до корня: условие цикла d * d <= n, и для каждого найденного записывают оба числа d и n // d. Для около миллиона это 1000 шагов вместо миллиона. Если — квадрат, при оба числа пары совпадают, и множество set хранит его один раз.
Пример
Найдите все делители числа 100.
- 1., перебираем от 1 до 10.
- 2.100 делится на 1, 2, 4, 5 и 10. Пары: 1 и 100, 2 и 50, 4 и 25, 5 и 20, 10 и 10.
- 3.Делитель 10 стоит в паре сам с собой, его считаем один раз. Всего 9 делителей.
- 4.Функция
divisors(n)собирает пары в множество,sortedпечатает их по возрастанию.
Ответ: 1, 2, 4, 5, 10, 20, 25, 50, 100
Сумма и количество делителей
Когда множество делителей собрано, его характеристики дают встроенные функции. sum(divisors(n)) — сумма всех делителей, len(divisors(n)) — их количество, max и min — наибольший и наименьший. Числа с ровно делителями отбирают условием len(divisors(n)) == k. Если делители 1 и не считают, уберите их из множества или вычтите из суммы.
Условие на последние цифры значения проверяют остатком: «оканчивается на 6» — r % 10 == 6, «оканчивается на 30» — r % 100 == 30. Последние цифры числа разобраны в теме последняя цифра.
Пример задания
Открытый банк ФИПИ
Пусть R – сумма всех различных натуральных делителей целого числа.
Напишите программу, которая перебирает целые числа, бóльшие 500 000, в порядке возрастания и ищет среди них такие, для которых значение R оканчивается на цифру 6. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – пять соответствующих этим числам значений R.
Например, для числа 20 R = 1 + 2 + 4 + 5 + 10 + 20 = 42.
Количество строк в таблице для ответа избыточно.
Наименьший и наибольший делитель, кроме 1 и самого числа
Наименьший делитель числа , больший 1, — первое от 2, на которое делится. Он всегда простой: у него нет меньших делителей, иначе они делили бы и . Наибольший делитель, меньший , стоит с ним в одной паре и равен n // d. Значит, оба крайних делителя находит один цикл, который останавливается на первом найденном .
Если цикл дошёл до и не нашёл делителя, число простое и таких делителей нет. Тогда функция возвращает 0, как требует условие задачи. Для наименьший делитель 3, наибольший , их сумма , разность .
Пример
— сумма наименьшего и наибольшего натуральных делителей числа, не считая единицы и самого числа; если таких делителей нет, . Найдите первые три числа, большие 600 000, для которых оканчивается на 12, и значения .
- 1.Функция
M(n)перебирает от 2 до и на первом делителе возвращаетd + n // d. - 2.Если делитель не найден, простое, функция возвращает 0.
- 3.«Оканчивается на 12» — две последние цифры:
m % 100 == 12. - 4.Цикл увеличивает с 600 001 и останавливается после трёх найденных чисел.
Ответ: 600007 7312, 600020 300012, 600027 200012
Перебор в порядке убывания и условие кратности
Если в условии «числа, меньшие 800 000, в порядке убывания», цикл начинают с границы и в начале каждого шага уменьшают число: n -= 1. Первое проверенное число — 799 999, сама граница не входит. Строки ответа идут в порядке убывания, как их печатает программа.
Условие «значение кратно 17» проверяют как f % 17 == 0. Но 0 тоже даёт остаток 0, а у простых чисел значение равно 0. Если условие говорит, что ноль не кратен, добавьте f != 0.
Пример
— разность наибольшего и наименьшего натуральных делителей числа, не считая единицы и самого числа; если таких делителей нет, . Перебирая числа, меньшие 500 000, в порядке убывания, найдите первые три числа, для которых кратно 19 (ноль числу 19 не кратен).
- 1.Функция
F(n)устроена какM(n)из предыдущего примера, но возвращаетn // d - d. - 2.Цикл начинает с
n = 500000и уменьшаетnдо проверки, поэтому первым проверяется 499 999. - 3.Условие
f != 0 and f % 19 == 0отбрасывает простые числа.
Ответ: 499970 249983, 499932 249964, 499915 99978
Простое число и проверка простоты
Простое число — натуральное число, у которого ровно два различных делителя: 1 и оно само. 1 не простое число: у неё один делитель. Число больше 1, которое не простое, называют составным.
Простоту проверяют перебором: если ни одно от 2 до не делит , число простое. Делителя больше корня без пары меньше корня не бывает, поэтому дальше искать не нужно. Функция is_prime(n) сначала отбрасывает числа меньше 2, затем возвращает False на первом найденном делителе.
Пример
Простые ли числа 221 и 223?
- 1., . Для обоих чисел перебираем от 2 до 14.
- 2.: делитель 13 найден, 221 составное.
- 3.223 не делится ни на одно число от 2 до 14, значит, 223 простое.
- 4.Программа печатает
False True.
Ответ: 221 составное, 223 простое
Простой ли наибольший делитель
Наибольший делитель числа , не равный , — это n // p, где — наименьший делитель больше 1. У простого такой делитель равен 1, и условие задачи считает, что его нет. Функция возвращает для простого числа 0, и такие числа пропускают условием m != 0: иначе 1 прошла бы проверку «не является простым». Простоту самого делителя проверяет функция is_prime из предыдущего блока.
Пример задания
Открытый банк ФИПИ
Напишите программу, которая перебирает целые числа, большие 350000, в порядке возрастания и ищет среди них такие, для которых наибольший натуральный делитель, не равный самому числу, не является простым числом. Программа должна найти и вывести первые 6 таких чисел и соответствующие им значения упомянутых делителей. Формат вывода: для каждого из 6 таких найденных чисел в отдельной строке сначала выводится само число, затем упомянутый делитель. Строки выводятся в порядке возрастания найденных чисел.
Например, для числа 105 наибольший натуральный делитель 35 не является простым, для числа 15 наибольший натуральный делитель 5 — простое число, а для числа 13 такого делителя не существует.
Разложение на простые множители
Каждое натуральное число больше 1 раскладывается в произведение простых множителей, и только одним способом: . Чтобы найти разложение, делите на , пока делится, и записывайте каждый раз. Затем увеличьте на 1 и повторите. Составное никогда не разделит остаток: его простые множители уже вынесены.
Цикл идёт, пока d * d <= n, где — уже уменьшенный остаток. Если после цикла остаток больше 1, он простой и становится последним множителем. «Число — произведение ровно двух простых множителей, не обязательно различных» значит, что в списке множителей ровно два элемента: len(f) == 2.
Пример
Перебирая числа, большие 1 103 285 717, найдите первые пять чисел, которые равны произведению ровно двух простых множителей (не обязательно различных), и каждый множитель ровно один раз содержит в записи 16. Для каждого числа укажите наименьший множитель.
- 1.Функция
factors(n)возвращает список простых множителей в порядке возрастания. - 2.Число подходит, если в списке два элемента и в записи каждого
str(p).count('16') == 1. - 3.Первый элемент списка — наименьший множитель.
- 4.Для 1 103 299 319 разложение : в обоих множителях 16 встречается один раз.
Ответ: 1103299319 1693, 1103309477 1693, 1103322107 16187, 1103323021 1693, 1103328547 3169
Решето Эратосфена
Решето Эратосфена находит все простые числа от 2 до сразу. Выпишите числа от 2 до . Возьмите первое незачёркнутое число : оно простое. Зачеркните все числа, кратные , начиная с : меньшие кратные уже зачёркнуты как кратные меньших простых. Повторяйте, пока . Незачёркнутые числа — простые.
В программе вместо зачёркивания хранят список is_prime из значений True и ставят False в кратные. Решето выгодно, когда нужна простота многих чисел одного диапазона: каждое число проверяется одним обращением к списку.
Пример
Найдите все простые числа, не больше 50, решетом Эратосфена.
- 1.: зачёркиваем 4, 6, 8, …, 50.
- 2.: зачёркиваем 9, 15, 21, … — 12, 18 и другие чётные уже зачёркнуты.
- 3.: зачёркиваем 25, 35, 45. : , зачёркиваем 49.
- 4.Следующее незачёркнутое число 11, , остановка.
Ответ: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47