Статья Автор: Лебедев Дмитрий

(The Last Inch) КЕГЭ- 25. Модель решения

Задание 25

Для решения задания потребуется умение проверять число на простату и умение определять все делители числа.
Будем использовать программу mindel, которая будет возвращать минимальный простой делитель числа и поиск делителей числа.

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

Программа mindel возвращает минимальный простой делитель для всех чисел больших 1.
Число будет простым, если mindel(n) == n.
Теперь несложно составить всю программу (приведем "наивное" решение - усовершенствование поиска всех делителей)

def mindel(n): # поиск минимального делителя
    if n % 2 == 0 : return 2
    if n < 9 : return n
    d = 1
    while d * d < n :
        d += 2
        if n % d == 0 : return d
    return n
N, k = 23600000, 6 # параметры задания
a, b = 213, 171
while k > 0 : # шаблон поиска k элементов
    N +=1 # увеличение N
    m0, m1 = N, 0 # инициализация мин и мах для удобной проверки
    d = 1 # начальное значение делителя
    while d*d < N : # перебор всех делителей
        d += 1 # увеличение кандидата в делители
        if N % d != 0 : continue # не делитель
        x, y = d, N// d # очередная пара делителей
        if x == mindel(x) : # x - простое
            m0 = min(m0 , x)
            m1 = max(m1 , x)
        if y == mindel(y) : # y - простое
            m0 = min(m0 , y)
            m1 = max(m1 , y)
            
    if m0*m1 == 0 : continue # один из делителей ещё не найден
    M = m0 + m1 # определяем сумму делителей
    if M % a != b : continue # сумма не удовлетворяет требованиям
    print(k, N, M) # вывод очередного результата
    k -= 1 # уменьшение требований к поиску

Решение можно ускорить, если провести "факторизацию" - сохраняя только простые делители.
Кроме уменьшения времени работы в 15 раз, снижается вероятность ошибки:
- в первом решении можно допустить логическую ошибку - посчитать, что минимальный простой делитель меньше корня из N (это верно), а максимальный не меньше корня из N (а это неверно - смотри результаты работы программы)

def mindel(n): # поиск минимального делителя
    if n % 2 == 0 : return 2
    if n < 9 : return n
    d = 1
    while d * d < n :
        d += 2
        if n % d == 0 : return d
    return n
def factor(n) : # программа факторизации числа (не полная - только делители)
    A = []
    while n > 1 :
        d = mindel(n)
        while n % d == 0 : 
            n = n//d
        A.append(d)
    return A    
N, k = 23600000, 6 # параметры задания
a, b = 213, 171
while k > 0 : # шаблон поиска k элементов
    N +=1 # увеличение N
    A = factor(N) # факторизация N
    m0, m1 = min(A), max(A) # определение минимального и максимального простого делителя 
    if m1 == N : continue
    M = m0 + m1 # определяем сумму делителей
    if M % a != b : continue # сумма не удовлетворяет требованиям
    print(k, N, M, m0, m1) # вывод очередного результата
    k -= 1 # уменьшение требований к поиску

Задача 25 (19779)
Среди чисел больших 55 000 000, найдите такие, что среди их простых делителей есть число, оканчивающееся на 777, при этом не равное самому числу.
В качестве ответа приведите 4 наименьших числа, соответствующих условию.
Формат вывода: для каждого из 4 таких найденных чисел в отдельной строке сначала выводится само число, затем минимальный простой делитель, оканчивающийся на 777, не равный самому числу.
Количество строк для записи ответа избыточно.

def mindel(n): # поиск минимального делителя
    if n % 2 == 0 : return 2
    if n < 9 : return n
    d = 1
    while d * d < n :
        d += 2
        if n % d == 0 : return d
    return n
def fact777(n, a) : # программа факторизации числа (не полная - только делители)
    while n > 1 :
        d = mindel(n)
        while n % d == 0 : 
            n = n//d
        if d  % 1000 == a :
            return d
    return 0    
N, k = 55000000, 4 # параметры задания
a = 777
while k > 0 : # шаблон поиска k элементов
    N +=1 # увеличение N
    A = fact777(N, a) # факторизация N
    if A == 0 or A == N : continue
    print(N, A, N/A) # вывод очередного результата
    k -= 1 # уменьшение требований к поиску

# Это авторское решение с компегэ для задания 19779 - для сравнения
def div(x):
    d = set()
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            d.add(i)
            d.add(x//i)
    return sorted(d)

k = 0
for x in range(55_000_001,55_010_000):
    d = [i for i in div(x) if len(div(i))==0 and i%1000==777]
    if len(d)>0:
        print(x,d[0])
        k += 1
        if k==4: break

# Это авторское решение с компегэ для задания 19776 - для сравнения
def div(x):
    d = set()
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            d.add(i)
            d.add(x//i)
    return sorted(d)

k = 0
for x in range(23_600_001,23_601_000):
    d = [i for i in div(x) if len(div(i))==0]
    M = d[0]+d[-1] if len(d)>0 else 0
    if M%213==171:
        print(x,M)
        k += 1
        if k==6: break

Печать