Задание 25
тема 2 из 4

Делители и простые числа

Делители числа идут парами d и n / d, поэтому их ищут перебором только до квадратного корня из числа. Наименьший делитель, больший единицы, всегда простой, а наибольший делитель, меньший самого числа, получается делением на него. Простоту проверяют тем же перебором, разложение на множители — делением в цикле, а все простые числа диапазона даёт решето Эратосфена.

Главная тема в задании25На карте навыков

Как искать делители

Число dd — делитель числа nn, если nn делится на dd без остатка: n % d == 0.

  • Делители идут парами dd и n/dn / d, меньший из пары не больше n\sqrt{n}. Перебирайте dd от 1, пока d * d <= n, и берите оба делителя пары.
  • Наименьший делитель больше 1 — первый dd от 2, на который nn делится. Наибольший делитель меньше nn равен n/dn / d.
  • Число простое, если n>1n > 1 и ни одно dd от 2 до n\sqrt{n} его не делит.
  • Разложение на простые множители: делите nn на dd, пока делится, затем увеличивайте dd. Остаток больше 1 — последний простой множитель.
  • Перебор чисел: цикл while со счётчиком найденных чисел, остановка после нужного количества.

Делители парами: перебор до корня

Делитель натурального числа nn — натуральное число dd, на которое nn делится без остатка. В Python это условие n % d == 0. У каждого n>1n > 1 есть делители 1 и nn.

Если dd — делитель, то n/dn / d тоже делитель: d⋅(n/d)=nd \cdot (n / d) = n. В каждой паре меньший делитель не больше n\sqrt{n}, иначе произведение пары было бы больше nn. Поэтому делители перебирают только до корня: условие цикла d * d <= n, и для каждого найденного dd записывают оба числа d и n // d. Для nn около миллиона это 1000 шагов вместо миллиона. Если nn — квадрат, при d=nd = \sqrt{n} оба числа пары совпадают, и множество set хранит его один раз.

Пример

Найдите все делители числа 100.

  1. 1.100=10\sqrt{100} = 10, перебираем dd от 1 до 10.
  2. 2.100 делится на 1, 2, 4, 5 и 10. Пары: 1 и 100, 2 и 50, 4 и 25, 5 и 20, 10 и 10.
  3. 3.Делитель 10 стоит в паре сам с собой, его считаем один раз. Всего 9 делителей.
  4. 4.Функция divisors(n) собирает пары в множество, sorted печатает их по возрастанию.

Ответ: 1, 2, 4, 5, 10, 20, 25, 50, 100

Сумма и количество делителей

Когда множество делителей собрано, его характеристики дают встроенные функции. sum(divisors(n)) — сумма всех делителей, len(divisors(n)) — их количество, max и min — наибольший и наименьший. Числа с ровно kk делителями отбирают условием len(divisors(n)) == k. Если делители 1 и nn не считают, уберите их из множества или вычтите из суммы.

Условие на последние цифры значения проверяют остатком: «оканчивается на 6» — r % 10 == 6, «оканчивается на 30» — r % 100 == 30. Последние цифры числа разобраны в теме последняя цифра.

Пример задания

Открытый банк ФИПИ

Пусть R – сумма всех различных натуральных делителей целого числа.
Напишите программу, которая перебирает целые числа, бóльшие 500 000, в порядке возрастания и ищет среди них такие, для которых значение R оканчивается на цифру 6. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – пять соответствующих этим числам значений R.

Например, для числа 20 R = 1 + 2 + 4 + 5 + 10 + 20 = 42.
Количество строк в таблице для ответа избыточно.

Наименьший и наибольший делитель, кроме 1 и самого числа

Наименьший делитель числа nn, больший 1, — первое dd от 2, на которое nn делится. Он всегда простой: у него нет меньших делителей, иначе они делили бы и nn. Наибольший делитель, меньший nn, стоит с ним в одной паре и равен n // d. Значит, оба крайних делителя находит один цикл, который останавливается на первом найденном dd.

Если цикл дошёл до n\sqrt{n} и не нашёл делителя, число простое и таких делителей нет. Тогда функция возвращает 0, как требует условие задачи. Для n=105n = 105 наименьший делитель 3, наибольший 105/3=35105 / 3 = 35, их сумма M=38M = 38, разность F=32F = 32.

Пример

MM — сумма наименьшего и наибольшего натуральных делителей числа, не считая единицы и самого числа; если таких делителей нет, M=0M = 0. Найдите первые три числа, большие 600 000, для которых MM оканчивается на 12, и значения MM.

  1. 1.Функция M(n) перебирает dd от 2 до n\sqrt{n} и на первом делителе возвращает d + n // d.
  2. 2.Если делитель не найден, nn простое, функция возвращает 0.
  3. 3.«Оканчивается на 12» — две последние цифры: m % 100 == 12.
  4. 4.Цикл увеличивает nn с 600 001 и останавливается после трёх найденных чисел.

Ответ: 600007 7312, 600020 300012, 600027 200012

Перебор в порядке убывания и условие кратности

Если в условии «числа, меньшие 800 000, в порядке убывания», цикл начинают с границы и в начале каждого шага уменьшают число: n -= 1. Первое проверенное число — 799 999, сама граница не входит. Строки ответа идут в порядке убывания, как их печатает программа.

Условие «значение кратно 17» проверяют как f % 17 == 0. Но 0 тоже даёт остаток 0, а у простых чисел значение равно 0. Если условие говорит, что ноль не кратен, добавьте f != 0.

Пример

FF — разность наибольшего и наименьшего натуральных делителей числа, не считая единицы и самого числа; если таких делителей нет, F=0F = 0. Перебирая числа, меньшие 500 000, в порядке убывания, найдите первые три числа, для которых FF кратно 19 (ноль числу 19 не кратен).

  1. 1.Функция F(n) устроена как M(n) из предыдущего примера, но возвращает n // d - d.
  2. 2.Цикл начинает с n = 500000 и уменьшает n до проверки, поэтому первым проверяется 499 999.
  3. 3.Условие f != 0 and f % 19 == 0 отбрасывает простые числа.

Ответ: 499970 249983, 499932 249964, 499915 99978

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

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

Простоту проверяют перебором: если ни одно dd от 2 до n\sqrt{n} не делит nn, число простое. Делителя больше корня без пары меньше корня не бывает, поэтому дальше искать не нужно. Функция is_prime(n) сначала отбрасывает числа меньше 2, затем возвращает False на первом найденном делителе.

Пример

Простые ли числа 221 и 223?

  1. 1.142=19614^2 = 196, 152=22515^2 = 225. Для обоих чисел перебираем dd от 2 до 14.
  2. 2.221=13⋅17221 = 13 \cdot 17: делитель 13 найден, 221 составное.
  3. 3.223 не делится ни на одно число от 2 до 14, значит, 223 простое.
  4. 4.Программа печатает False True.

Ответ: 221 составное, 223 простое

Простой ли наибольший делитель

Наибольший делитель числа nn, не равный nn, — это n // p, где pp — наименьший делитель больше 1. У простого nn такой делитель равен 1, и условие задачи считает, что его нет. Функция возвращает для простого числа 0, и такие числа пропускают условием m != 0: иначе 1 прошла бы проверку «не является простым». Простоту самого делителя проверяет функция is_prime из предыдущего блока.

Пример задания

Открытый банк ФИПИ

Напишите программу, которая перебирает целые числа, большие 350000, в порядке возрастания и ищет среди них такие, для которых наибольший натуральный делитель, не равный самому числу, не является простым числом. Программа должна найти и вывести первые 6 таких чисел и соответствующие им значения упомянутых делителей. Формат вывода: для каждого из 6 таких найденных чисел в отдельной строке сначала выводится само число, затем упомянутый делитель. Строки выводятся в порядке возрастания найденных чисел. 
Например, для числа 105 наибольший натуральный делитель 35 не является простым, для числа 15 наибольший натуральный делитель 5 — простое число, а для числа 13 такого делителя не существует. 

Разложение на простые множители

Каждое натуральное число больше 1 раскладывается в произведение простых множителей, и только одним способом: 360=2⋅2⋅2⋅3⋅3⋅5360 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5. Чтобы найти разложение, делите nn на d=2d = 2, пока делится, и записывайте dd каждый раз. Затем увеличьте dd на 1 и повторите. Составное dd никогда не разделит остаток: его простые множители уже вынесены.

Цикл идёт, пока d * d <= n, где nn — уже уменьшенный остаток. Если после цикла остаток больше 1, он простой и становится последним множителем. «Число — произведение ровно двух простых множителей, не обязательно различных» значит, что в списке множителей ровно два элемента: len(f) == 2.

Пример

Перебирая числа, большие 1 103 285 717, найдите первые пять чисел, которые равны произведению ровно двух простых множителей (не обязательно различных), и каждый множитель ровно один раз содержит в записи 16. Для каждого числа укажите наименьший множитель.

  1. 1.Функция factors(n) возвращает список простых множителей в порядке возрастания.
  2. 2.Число подходит, если в списке два элемента и в записи каждого str(p).count('16') == 1.
  3. 3.Первый элемент списка — наименьший множитель.
  4. 4.Для 1 103 299 319 разложение 1693⋅6516831693 \cdot 651683: в обоих множителях 16 встречается один раз.

Ответ: 1103299319 1693, 1103309477 1693, 1103322107 16187, 1103323021 1693, 1103328547 3169

Решето Эратосфена

Решето Эратосфена находит все простые числа от 2 до NN сразу. Выпишите числа от 2 до NN. Возьмите первое незачёркнутое число pp: оно простое. Зачеркните все числа, кратные pp, начиная с p2p^2: меньшие кратные уже зачёркнуты как кратные меньших простых. Повторяйте, пока p2≤Np^2 \le N. Незачёркнутые числа — простые.

В программе вместо зачёркивания хранят список is_prime из N+1N + 1 значений True и ставят False в кратные. Решето выгодно, когда нужна простота многих чисел одного диапазона: каждое число проверяется одним обращением к списку.

Пример

Найдите все простые числа, не больше 50, решетом Эратосфена.

  1. 1.p=2p = 2: зачёркиваем 4, 6, 8, …, 50.
  2. 2.p=3p = 3: зачёркиваем 9, 15, 21, … — 12, 18 и другие чётные уже зачёркнуты.
  3. 3.p=5p = 5: зачёркиваем 25, 35, 45. p=7p = 7: 72=497^2 = 49, зачёркиваем 49.
  4. 4.Следующее незачёркнутое число 11, 112=121>5011^2 = 121 > 50, остановка.

Ответ: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Потренируйте навык

Все задания на этот навык

Решать