Задание 25 ЕГЭ: произведение двух простых чисел

Произведение ровно двух простых множителей с условием. Тема номера — делители и маски чисел. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Напишите программу, которая перебирает целые числа, бо́льшие 497 237, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых оканчивается на цифру 3.

В ответе в первом столбце таблицы запишите первые 5 найденных чисел в порядке возрастания, а во втором столбце – для каждого из них соответствующий наибольший найденный множитель.

Запишите каждую пару чисел с новой строки: сначала найденное число, затем через пробел — его наибольший множитель.

Решение

Для числа n находим наименьший делитель p, больший 1 (он простой). Число — произведение ровно двух простых, если p < n и частное q = n // p тоже простое. Сначала проверяем условие для p (это дёшево), потом условие и простоту для q. Во втором столбце — q: при p ≤ q это наибольший множитель.

def min_div(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return d
        d += 1
    return n


n = 497237
found = 0
while found < 5:
    n += 1
    p = min_div(n)
    if p == n or p % 10 != 3:
        continue
    q = n // p
    if q % 10 == 3 and min_div(q) == q:
        print(n, q)
        found += 1

Ответ:
497489 1123
497499 165833
497549 38273
497649 165883
497939 38303

Решить такую задачу — новый вариант с проверкой