Подтема 4 из 6
Простые числа и разложение
Проверка простоты, разложение на простые множители, простые делители и задача темы о произведении двух простых.
Простые числа
Какое число простое и как это быстро проверить?
Простое число больше 1 и делится только на 1 и на себя. Делитель достаточно искать от 2 до √n: не нашёлся — число простое. Это тот же поиск до корня, что в подтеме 2, только останавливаемся на первом найденном делителе. Простые числа — 2, 3, 5, 7, 11, 13, …; 12 составное, а 1 — ни то ни другое: делитель у неё один.
def is_prime(n): if n < 2: return False for d in range(2, isqrt(n) + 1): if n % d == 0: return False return True print(is_prime(1), is_prime(2), is_prime(49), is_prime(97))return True стоит после цикла, а не внутри: одна неудачная попытка ещё ничего не доказывает. 25 не делится на 2, но делится на 5. У 2 цикл не выполнится ни разу — кандидатов от 2 до isqrt(2) = 1 нет, — и функция честно вернёт True.
Разложение на множители
Из каких простых чисел составлено число — и как это найти?
Делить на 2, пока делится, потом на 3, на 4 и дальше. Каждое удачное деление даёт простой множитель, а то, что осталось больше 1 после цикла, — последний множитель. 360 делится на 2 трижды: 360 → 180 → 90 → 45. Потом на 3 дважды: 45 → 15 → 5. Осталось простое 5. В тетради так раскладывают лесенкой:
Программа делает то же самое:
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 print(prime_factors(360), prime_factors(7000421))m — то, что осталось от числа; m //= d — это m = m // d. Внутренний while, а не if: иначе из 360 ушла бы одна двойка из трёх. Второе число — первое из ответа задачи темы: 7 000 421 = 61 · 114 761. Посмотри по шагам, как раскладывается 1050:
- Начинаем: m = 1050, первый кандидат d = 2.
- 1050 делится на 2: записываем 2, теперь m = 525. Не меняем d: вдруг делится ещё раз.
- 525 на 2 не делится — переходим к d = 3.
- 525 делится на 3: записываем 3, теперь m = 175. Не меняем d: вдруг делится ещё раз.
- 175 на 3 не делится — переходим к d = 4.
- 175 на 4 не делится — переходим к d = 5. Составное 4 делить не может: все двойки уже удалены из m.
- 175 делится на 5: записываем 5, теперь m = 35. Не меняем d: вдруг делится ещё раз.
- 35 делится на 5: записываем 5, теперь m = 7. Снова тот же множитель — поэтому внутри стоит while, а не if.
- 5 · 5 = 25 больше m = 7 — цикл закончен. Если бы у 7 был делитель больше 1, хотя бы один нашёлся бы не больше √7, а такие кандидаты уже проверены.
- После цикла осталось m = 7. Делителей у него нет, значит, 7 простое — дописываем его. Итог: 1050 = 2 · 3 · 5 · 5 · 7.
На d = 4 ничего не делится: двойка уже вынута, и составному кандидату делить нечего. Поэтому в список попадают только простые числа, хотя d перебирает все подряд. Цикл кончается, когда d · d больше остатка, — у 1050 остаётся 7, оно и есть последний множитель.
Обоснование · необязательноПочему остаток после цикла — простое число
Если бы остаток m был составным, у него нашёлся бы делитель не больше √m — цикл до него дошёл бы и разделил. Раз цикл закончился, а m > 1, у m нет делителей до корня, значит, оно простое.
Простые делители
Условие спрашивает о простых делителях: наибольшем, их сумме или количестве. Где их взять?
В разложении: простые делители — это его множители без повторов. убирает повторы, sorted выстраивает по возрастанию.
P = sorted(set(prime_factors(84)))print(prime_factors(84), P)Это быстрее, чем искать все делители и проверять каждый на простоту. Дальше всё считается по списку P — выбери, что требуется:
- наименьший
P[0]→ 2- наибольший
P[-1]→ 7- наименьший + наибольший
P[0] + P[-1]→ 9- сумма
sum(P)→ 12- количество
len(P)→ 3
«Не считая самого числа» важно только для простых чисел: у 97 разложение — [97], и без самого числа простых делителей не остаётся. Величину тогда берут такой, как велит условие, обычно 0. У 49 = 7 · 7 делитель 7 не равен самому числу и остаётся.
Множители и делители
«Произведение ровно двух простых множителей» и «ровно два различных простых делителя» — это одно и то же?
Нет. Множители считают с повторами — len(f), различные делители без повторов — len(set(f)). Здесь f = prime_factors(n):
| Число | Разложение | len(f) | len(set(f)) |
|---|---|---|---|
| 15 | 3 · 5 | 2 | 2 |
| 9 | 3 · 3 | 2 | 1 |
| 12 | 2 · 2 · 3 | 3 | 2 |
| 30 | 2 · 3 · 5 | 3 | 3 |
«Ровно два простых множителя, не обязательно различных» — подходят 15 и 9. «Ровно два различных простых делителя» — 15 и 12. Слова «не обязательно различных» разрешают квадраты простых: 9 = 3 · 3, 3721 = 61 · 61.
Задача темы
Вернёмся к задаче темы:
«Напишите программу, которая перебирает целые числа, большие 7 000 000, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых содержит в своей записи хотя бы одну цифру 1 и хотя бы одну цифру 6. В ответе для первых пяти найденных чисел запишите само число и наибольший из его простых множителей.»
Всё готово: перебор вверх от 7 000 001 до пяти найденных, разложение каждого числа, ровно два множителя и цифры 1 и 6 в каждом из них. Проверку цифр мы написали в подтеме 1 — функция has_1_and_6.
Сначала проверим программу там, где ответ можно найти вручную. Простые числа с цифрами 1 и 6 — это 61, 163, 167, … (16 и 106 не простые). Самые маленькие произведения двух таких чисел: 61 · 61 = 3721, 61 · 163 = 9943, 61 · 167 = 10 187. Значит, после 3000 программа должна найти именно эти три числа:
n = 3001found = 0while found < 3: f = prime_factors(n) if len(f) == 2 and has_1_and_6(f[0]) and has_1_and_6(f[1]): print(n, f) found += 1 n += 1Совпало, и 3721 = 61 · 61 тоже нашлось: множители не обязаны быть различными. Меняем границу и количество — и печатаем то, что просит условие, наибольший множитель:
n = 7_000_001found = 0while found < 5: f = prime_factors(n) if len(f) == 2 and has_1_and_6(f[0]) and has_1_and_6(f[1]): print(n, max(f)) found += 1 n += 1Ответ: 7000421 114761 7000691 2671 7000909 114769 7002643 42961 7003019 6551. Подчёркивание в 7_000_001 только для чтения — это то же число 7000001.
Программа проверила около трёх тысяч чисел и закончила меньше чем за секунду: у большинства чисел маленький множитель находится сразу, и до √n цикл идёт редко. Проверку двух множителей можно записать и короче — : «у всех множителей из f есть 1 и 6».
Итого
- Простоенет делителя от 2 до √n; 1 — не простое
- Разложениеделить на d, пока делится; остаток > 1 — множитель
- Простые делители
sorted(set(prime_factors(n))) - Множители с повторами
len(f) - Различные делители
len(set(f)) - Задача темысначала маленькая граница, потом настоящая
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
prime_factors(1960)? Какие у 1960 различные простые делители?ОтветСкрыть ответ
[2, 2, 2, 5, 7, 7]; различные простые делители — 2, 5 и 7.len(f) и len(set(f)) для 12 и для 9, если f = prime_factors(n)?ОтветСкрыть ответ
prime_factors внутренний while m % d == 0 заменили на if. Что вернёт функция для 72?ОтветСкрыть ответ
[2, 3, 12] вместо [2, 2, 2, 3, 3]: каждый d делит только один раз, остаток 12 уже меньше 4 · 4, цикл кончается, и составное 12 попадает в список как «множитель».ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Найди простые с простой суммой цифр
Найди на отрезке [251 000; 251 100] все простые числа, сумма цифр которых — тоже простое число. Для каждого выведи число и сумму его цифр.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке число и сумма его цифр.
Подсказка
is_prime ищет делитель от 2 до √n; ту же функцию примени к сумме цифр.
Решение
Например, 251 003 — простое, сумма цифр 2 + 5 + 1 + 0 + 0 + 3 = 11 — тоже простое.
Решение программой
from math import isqrt def is_prime(n): if n < 2: return False for d in range(2, isqrt(n) + 1): if n % d == 0: return False return True for n in range(251000, 251101): s = sum(int(ch) for ch in str(n)) if is_prime(n) and is_prime(s): print(n, s)Программа выведет
251003 11251063 17251081 17251087 23Ответ: 251003 11 251063 17 251081 17 251087 23
Найди числа с простой суммой делителей
Пусть R — сумма всех натуральных делителей числа, не считая единицы и самого числа; если таких делителей нет, R = 0. Найди пять наименьших чисел, больших 2 000 000, для которых R — простое число. Для каждого выведи число и R.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке число и R.
Подсказка
У простого числа R = 0 — оно не простое и не пройдёт. Делители даёт get_divisors, простоту R проверяет is_prime.
Решение
Перебираем числа после 2 000 000, для каждого складываем делители 1 < d < n и проверяем сумму на простоту.
Решение программой
from math import isqrt def is_prime(n): if n < 2: return False for d in range(2, isqrt(n) + 1): if n % d == 0: return False return True def get_divisors(n): divisors = [] for d in range(1, isqrt(n) + 1): if n % d == 0: divisors.append(d) if n // d != d: divisors.append(n // d) return sorted(divisors) n = 2000001found = 0while found < 5: R = sum(d for d in get_divisors(n) if 1 < d < n) if is_prime(R): print(n, R) found += 1 n += 1Программа выведет
2000016 43835032000034 25227172000070 32902012000074 10000392000076 3026147Ответ: 2000016 4383503 2000034 2522717 2000070 3290201 2000074 1000039 2000076 3026147
Разложи 1960 на простые множители
Разложи на простые множители 1960.
Введите множители через пробел в порядке неубывания, с повторениями.
Подсказка
Дели на 2, пока делится, затем на 3, 5, 7 и так далее.
Решение
1960 = 2 · 2 · 2 · 5 · 7 · 7 = 2³ · 5 · 7².
Решение программой
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] print(*prime_factors(1960))Ответ: 2 2 2 5 7 7
Найди наибольший простой делитель 999 999
Найди наибольший простой делитель числа 999 999.
Введите простой делитель.
Подсказка
Наибольший простой делитель — последний множитель разложения.
Решение
37: 999 999 = 3³ · 7 · 11 · 13 · 37.
Решение программой
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] print(max(prime_factors(999999)))Ответ: 37
Выпиши простые делители 990
Выпиши все различные простые делители числа 990.
Введите делители через пробел в порядке возрастания.
Подсказка
Простые делители — различные множители разложения.
Решение
2, 3, 5, 11: 990 = 2 · 3 · 3 · 5 · 11, повтор тройки в ответ не входит.
Решение программой
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] print(*prime_divisors(990))Ответ: 2 3 5 11
Найди пять чисел с суммой простых делителей на 7
Пусть S — сумма всех различных простых делителей числа, не считая самого числа. Если таких делителей нет, S = 0. Найди пять наименьших чисел, больших 2 500 000, для которых S не равно нулю, не больше 5000 и оканчивается цифрой 7. Для каждого выведи число и S.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке число и S.
Подсказка
S — сумма различных простых делителей без самого числа. У простого числа таких делителей нет, и S = 0.
Решение
Для каждого числа после 2 500 000 берём различные простые делители, кроме самого числа, и проверяем три условия на S: не ноль, не больше 5000, последняя цифра 7.
Решение программой
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 = 2500001found = 0while found < 5: S = sum(prime_divisors(n)) if S != 0 and S <= 5000 and S % 10 == 7: print(n, S) found += 1 n += 1Программа выведет
2500017 49472500100 11172500113 2372500148 31172500153 927Ответ: 2500017 4947 2500100 1117 2500113 237 2500148 3117 2500153 927
Найди пять чисел с простым M больше 1000
Пусть M — сумма наименьшего и наибольшего простых делителей числа, не считая самого числа. Найди пять наименьших чисел, больших 5 000 000, для которых M больше 1000 и является простым числом. Для каждого выведи число и M.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке число и M.
Подсказка
Простые делители уже отсортированы: наименьший — первый, наибольший — последний. Простоту M проверь отдельной функцией.
Решение
Для каждого числа после 5 000 000 берём различные простые делители, кроме самого числа, складываем наименьший и наибольший и проверяем, что сумма больше 1000 и проста.
Решение программой
from math import isqrt 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] def is_prime(n): if n < 2: return False for d in range(2, isqrt(n) + 1): if n % d == 0: return False return True n = 5000001found = 0while found < 5: P = prime_divisors(n) if P: M = P[0] + P[-1] if M > 1000 and is_prime(M): print(n, M) found += 1 n += 1Программа выведет
5000010 1666695000026 17895000034 49335000038 32535000066 4261Ответ: 5000010 166669 5000026 1789 5000034 4933 5000038 3253 5000066 4261
Сравни простые делители и множители 72
Для числа 72 определи количество различных простых делителей и количество простых множителей с учётом повторений.
Введите два числа через пробел: количество различных простых делителей и количество простых множителей с повторениями.
Подсказка
Разложи 72 и посчитай множители дважды: без повторов и с повторами.
Решение
Различных — 2 (это 2 и 3), с повторениями — 5 (2, 2, 2, 3, 3).
Решение программой
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] f = prime_factors(72)print(len(set(f)), len(f))Ответ: 2 5
Найди произведения трёх близких простых
Найди на отрезке [400 000; 700 000] все числа, которые являются произведением трёх различных простых множителей, причём наибольший и наименьший множители отличаются не больше чем на 12. Для каждого выведи число и эту разность.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке число и разность множителей.
Подсказка
Три различных множителя — len(f) == 3 и len(set(f)) == 3. Разложение отсортировано, разность — f[2] − f[0].
Решение
Например, 409 457 = 71 · 73 · 79, разность 79 − 71 = 8.
Решение программой
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 for n in range(400000, 700001): f = prime_factors(n) if len(f) == 3 and len(set(f)) == 3: if f[2] - f[0] <= 12: print(n, f[2] - f[0])Программа выведет
409457 8430189 12465547 12478661 10583573 10Ответ: 409457 8 430189 12 465547 12 478661 10 583573 10
Найди произведения двух простых с цифрой 7
Найди пять наименьших чисел, больших 3 000 000, которые представимы в виде произведения ровно двух простых множителей, не обязательно различных, причём каждый множитель содержит в записи цифру 7. Для каждого числа выведи его и наибольший из множителей.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке число и наибольший из множителей.
Подсказка
Разложение должно состоять ровно из двух множителей с повторениями, и цифра 7 должна быть в записи каждого — проверь это через all.
Решение
Длина разложения с повторениями равна 2 — это «ровно два простых множителя, не обязательно различных»; all проверяет цифру 7 у каждого.
Решение программой
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 = 3000001found = 0while found < 5: f = prime_factors(n) if len(f) == 2 and all("7" in str(p) for p in f): print(n, max(f)) found += 1 n += 1Программа выведет
3000053 4285793000059 447773000139 46373000241 110713000247 42257Ответ: 3000053 428579 3000059 44777 3000139 4637 3000241 11071 3000247 42257
Задача темы: два простых множителя с цифрами 1 и 6
Задача темы. Перебирай целые числа, большие 7 000 000, в порядке возрастания и найди среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых содержит в своей записи хотя бы одну цифру 1 и хотя бы одну цифру 6. Для первых пяти найденных чисел выведи само число и наибольший из его простых множителей.
Запишите все строки ответа подряд в одну строку через пробел: в каждой строке число и наибольший множитель.
Подсказка
Разложи число на простые множители: подходит, если их ровно два и в записи каждого есть 1 и 6. Проверь программу на границе 3000 — первым должно найтись 3721 = 61 · 61.
Решение
Перебор вверх от 7 000 001 до пяти найденных, разложение каждого числа и проверка цифр у обоих множителей. Например, 7 000 421 = 61 · 114 761: в 61 и в 114 761 есть и 1, и 6.
Решение программой
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 has_1_and_6(p): s = str(p) return '1' in s and '6' in s n = 7000001found = 0while found < 5: f = prime_factors(n) if len(f) == 2 and has_1_and_6(f[0]) and has_1_and_6(f[1]): print(n, max(f)) found += 1 n += 1Программа выведет
7000421 1147617000691 26717000909 1147697002643 429617003019 6551Ответ: 7000421 114761 7000691 2671 7000909 114769 7002643 42961 7003019 6551