Задание 25 · Обработка целочисленной информации
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Задача темы — первые пять чисел больше 7 000 000, равных произведению двух простых с цифрами 1 и 6, — собиралась из функций нескольких подтем. Пролистай версии: точками отмечены строки, которых не было в предыдущей.
- Подтема 1, «Перебор и запись числа»: первые пять — while и счётчик. Точками отмечены новые строки.
- Подтема 2, «Делители парами»: делители до √n парами.
- Подтема 4, «Разложение»: простые множители с повторами.
- Подтема 4, «Задача темы»: ровно два множителя, в каждом 1 и 6. Первое число задачи темы — 7 000 421 = 61 · 114 761.
Перебор везде один — меняется проверка числа. Подтема 3 считает делители и величину M, подтема 5 перебирает по маске с шагом, равным делителю, а дополнительный урок по числу делителей узнаёт вид числа, когда отрезок слишком большой для перебора.
Карта темы
Каждая подтема дала одну проверку или способ перебора, и любое решение собирается из них. Сверху — путь от кандидатов к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- Кандидатыотрезок, шаг или маска
- Проверкаделители, множители, запись
- Выводчто и в каком порядке
1Перебор и запись числа
- первые kwhile found < k, n растёт от границы
'6' in str(n)цифра в записи числа
2Делители парами
- d и n // dd только до isqrt(n)
- кореньдобавить один раз
3Числа с нужными делителями
- ровно klen(D) == k
- MM = 0 — отдельный случай, проверь простые
4Простые числа и разложение
len(f)множители с повторамиlen(set(f))различные простые делители
5Маски
- кратные krange(0, limit + 1, k)
- ? и *fnmatch или построить через product
6Вид числа по количеству делителейдополнительный урок
- 3 делителяэто p²
- огромный отрезокперебирать p, а не числа
Как решать
Любое задание 25 решается одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
for n in [1, 2, 12, 16, 49]: print(n, get_divisors(n), prime_factors(n))И оцени размер перебора до запуска: десять миллионов простых проверок — секунды, а миллион чисел около 10⁹ с поиском делителей до √n — 3 · 10¹⁰ шагов, слишком долго. Тогда ищи шаг, построение по маске или вид числа.
Частые ошибки
Семь ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- range(L, R)
range(L, R)→range(L, R + 1). Спроси себя: проверено ли само число R?подтема 1- корень дважды
- у 49 делители 1, 7, 7, 49 → корень добавляют один раз. Спроси себя: сколько делителей у 49?подтема 2
- D[-1] без sorted
- наибольший делитель — последний добавленный → список сортируют. Спроси себя: что получится у 30?подтема 2
- M = 0
- «M оканчивается на 0» пропускает простые → у простых M = 0 — тоже подходит. Спроси себя: не попало ли в ответ простое число?подтема 3
- if вместо while
- каждый множитель вынут один раз → while m % d == 0. Спроси себя: сколько множителей у 72?подтема 4
- пустая звёздочка
- вставка вместо * начата с длины 1 → * — любые цифры, даже ни одной. Спроси себя: проверено ли число без вставки?подтема 5
- ноль впереди
- первый ? маски получил 0 → число не начинается с нуля. Спроси себя: не стала ли запись короче маски?подтема 5
Итог
Тема пройдена: задача темы решена от перебора до пяти ответов. Вот что взять с собой.
- ПорядокКандидаты, проверка, малые числа, размер, вывод.
- ДелителиПарами до √n, корень один раз.
- Множителиwhile m % d == 0; len(f) и len(set(f)).
- МаскиШаг, равный делителю, и fnmatch.
- Задача темыПервое число — 7 000 421 = 61 · 114 761.
Проверьте себя
Ответь сначала сам, потом открой ответ.
Почему делители ищут только до √n?
ОтветСкрыть ответ
Делители идут парами d и n // d, и в каждой паре меньший не больше √n: найдя его, сразу получаем и второй.
prime_factors(3721) = [61, 61]. Подходит ли 3721 под «произведение ровно двух простых, не обязательно различных»?
ОтветСкрыть ответ
Да: len(f) == 2, повторы считаются. «Различных» было бы len(set(f)).
Числа до 10⁸, делящиеся на 1301 и подходящие под маску. Как перебирать?
ОтветСкрыть ответ
Шагом 1301: range(0, 10**8 + 1, 1301) — в 1301 раз меньше кандидатов, а маску проверяет fnmatch.
У каких чисел ровно три делителя?
ОтветСкрыть ответ
У квадратов простых: p² делится на 1, p и p².
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Найди числа с двумя делителями без 1 и n
Найди все числа на отрезке [500 035; 500 055], у которых ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого числа выведи эти делители в порядке возрастания.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке число и два его делителя по возрастанию.
Подсказка
Отбери делители 1 < d < n и проверь, что их ровно два; выводить нужно и число, и делители.
Решение
Для каждого числа отрезка оставляем делители 1 < d < n и берём числа, у которых их ровно два. Подтемы 2 и 3: делители парами и отбор «без 1 и самого числа».
Решение программой
from math import isqrt def get_divisors(n): divisors = [] for d in range(1, isqrt(n) + 1): if n % d == 0: divisors.append(d) q = n // d if q != d: divisors.append(q) return sorted(divisors) for n in range(500035, 500056): D = [d for d in get_divisors(n) if 1 < d < n] if len(D) == 2: print(n, *D)Программа выведет
500037 3 166679500039 673 743500051 101 4951500053 71 7043500054 2 250027Ответ: 500037 3 166679 500039 673 743 500051 101 4951 500053 71 7043 500054 2 250027
Найди пять чисел с наибольшим простым делителем на 7
Пусть M — наибольший простой делитель числа, не считая самого числа. Если таких делителей нет, M = 0. Найди пять наименьших чисел, больших 1 200 000, для которых M больше нуля, не превышает 1000 и оканчивается цифрой 7. Для каждого выведи число и M.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке число и M.
Подсказка
Наибольший простой делитель — последний множитель разложения, если он не равен самому числу. Перебирай числа после 1 200 000, пока не найдёшь пять.
Решение
M — наибольший из различных простых делителей, кроме самого числа; у простого числа таких делителей нет, и M = 0. Подтема 4: простые делители через разложение.
Решение программой
def prime_factors(n): factors = [] m = n d = 2 while d * d <= m: while m % d == 0: factors.append(d) m //= d d += 1 if m > 1: factors.append(m) return factors def prime_divisors(n): P = sorted(set(prime_factors(n))) return [p for p in P if p != n] n = 1200001found = 0while found < 5: P = prime_divisors(n) M = max(P) if P else 0 if 0 < M <= 1000 and M % 10 == 7: print(n, M) found += 1 n += 1Программа выведет
1200047 9671200065 6171200082 4571200090 3671200108 157Ответ: 1200047 967 1200065 617 1200082 457 1200090 367 1200108 157
Найди кратные 1301 по маске 8?4*21
Среди натуральных чисел, не превышающих 10⁸, найди все числа, соответствующие маске 8?4*21 и делящиеся на 1301. Выведи числа в порядке возрастания и частные от деления на 1301.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке число и частное от деления на 1301.
Подсказка
Перебери только кратные 1301 до 10⁸ и проверь маску через fnmatch.
Решение
Кратных 1301 до 10⁸ меньше 77 000, поэтому их можно перебрать и проверить маску у каждого. Подтема 5: перебор кратных 1301 и проверка маски.
Решение программой
from fnmatch import fnmatch for n in range(1301, 10**8 + 1, 1301): if fnmatch(str(n), "8?4*21"): print(n, n // 1301)Программа выведет
8744021 672180429121 6182181469921 6262183421421 6412184462221 6492186413721 6642187454521 6722188495321 6802189406021 68721Ответ: 8744021 6721 80429121 61821 81469921 62621 83421421 64121 84462221 64921 86413721 66421 87454521 67221 88495321 68021 89406021 68721
Найди произведения трёх простых с цифрой 3
Найди пять наименьших чисел, больших 1 000 000, которые представимы в виде произведения ровно трёх простых множителей, не обязательно различных, и каждый множитель содержит в записи цифру 3. Для каждого выведи число и его множители.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке число и его три множителя по неубыванию.
Подсказка
Разложение должно состоять ровно из трёх множителей с повторами, и цифра 3 — в записи каждого.
Решение
Разложение с повторениями должно состоять ровно из трёх множителей, и в записи каждого есть цифра 3. Подтема 4: длина разложения с повторениями и all для цифр.
Решение программой
def prime_factors(n): factors = [] m = n d = 2 while d * d <= m: while m % d == 0: factors.append(d) m //= d d += 1 if m > 1: factors.append(m) return factors def prime_divisors(n): P = sorted(set(prime_factors(n))) return [p for p in P if p != n] n = 1000001found = 0while found < 5: f = prime_factors(n) if len(f) == 3 and all("3" in str(p) for p in f): print(n, *f) found += 1 n += 1Программа выведет
1000029 3 31 107531000077 3 13 256431000137 3 43 77531000287 3 3 1111431000383 3 139 2399Ответ: 1000029 3 31 10753 1000077 3 13 25643 1000137 3 43 7753 1000287 3 3 111143 1000383 3 139 2399
Найди число с наибольшим количеством делителей
Среди чисел отрезка [200 000; 200 100] найди число с наибольшим количеством натуральных делителей; если таких несколько, выбери наименьшее. Выведи количество делителей и само число.
Введите количество делителей и само число через пробел.
Подсказка
Храни лучшее количество делителей и заменяй его только при строго большем — при равенстве останется наименьшее число.
Решение
80 200070. Лучший результат заменяется только при строго большем количестве делителей, поэтому при равенстве остаётся наименьшее число. Подтема 3: хранение лучшего результата.
Решение программой
from math import isqrt def count_divisors(n): count = 0 for d in range(1, isqrt(n) + 1): if n % d == 0: if d * d == n: count += 1 else: count += 2 return count best_count = 0best_n = 0for n in range(200000, 200101): count = count_divisors(n) if count > best_count: best_count = count best_n = nprint(best_count, best_n)Ответ: 80 200070