Задание 25

Умение создавать собственные программы (10–20 строк) для обработки целочисленной информации · 25 заданий

Задание №25
№25
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: – символ «?» означает ровно одну произвольную цифру…
Алгоритмы обработки чисел
Задание №25
№25
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: 1) символ «?» означает ровно одну произвольную цифр…
Алгоритмы обработки чисел
Задание №25
№25
Пусть M — сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, т…
Алгоритмы обработки чисел
Задание №25
№25
Напишите программу, которая перебирает целые числа, большие 350000, в порядке возрастания и ищет среди них такие, для которых наибольший натуральный д…
Алгоритмы обработки чисел
Задание №25
№25
Напишите программу, которая перебирает целые числа, большие 450000, в порядке возрастания и ищет среди них такие, для которых наибольший натуральный д…
Алгоритмы обработки чисел
Задание №25
№25
Напишите программу, которая перебирает целые числа, большие 550 000, в порядке возрастания и ищет среди них такие, для которых наибольший натуральный…
Алгоритмы обработки чисел
Задание №25
№25
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: 1) символ «?» означает ровно одну произвольную цифр…
Алгоритмы обработки чисел
Задание №25
№25
Пусть F — разность максимального и минимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет…
Алгоритмы обработки чисел
Задание №25
№25
Пусть М - разность максимального и минимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет…
Алгоритмы обработки чисел
Задание №25
№25
Пусть М - разность максимального и минимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет…
Алгоритмы обработки чисел
Задание №25
№25
Пусть М - разность максимального и минимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет…
Алгоритмы обработки чисел
Задание №25
№25
Пусть F - разность максимального и минимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет…
Алгоритмы обработки чисел

Задание №25 — Проверка делимости

Пусть F — разность максимального и минимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то считаем значение F равным нулю.
Напишите программу, которая перебирает целые числа, большие 850 000, в порядке возрастания и ищет среди них такие, для которых значение F не равно нулю и делится нацело на 11. Программа должна найти и вывести первые 6 таких чисел и соответствующие им значения F.
Формат вывода: для каждого из 6 таких найденных чисел в отдельной строке сначала выводится само число, затем значение F. Строки выводятся в порядке возрастания найденных чисел.
Например, для числа 105 F = 35 - 3 = 32.

Правильный ответ

850018 425007 850019 29282 850023 283338 850040 425018 850062 425029 850084 425040

Пояснение

Решение:

Ключевое наблюдение: наименьший делитель числа $n$ , не равный 1, — это его наименьший простой делитель $p$ , а наибольший делитель, не равный $n$ , — это $n/p$ . Действительно, если $d$ — делитель, то $n/d$ — тоже делитель, и наименьшему делителю соответствует наибольший. Значит $F=\frac{n}{p}-p,$ а если $n$ простое, то «средних» делителей нет и $F=0$ .

Поэтому искать $p$ достаточно перебором до $\sqrt{n}$ : для $n\approx 850\,000$ это менее 1000 шагов, и вся программа отрабатывает мгновенно.

Перебираем числа, большие 850 000, по возрастанию и выводим первые 6 таких, у которых $F\ne 0$ и $F$ делится на 11.

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

n = 850000
found = 0
while found < 6:
    n += 1
    f = F(n)
    if f != 0 and f % 11 == 0:
        print(n, f)
        found += 1

Проверим пару строк вручную. Для

n=850018

наименьший простой делитель

p=2

, значит

F=425009-2=425007=11\cdot 38637

. Для

n=850019

наименьший простой делитель

p=29

F=850019/29-29=29311-29=29282=11\cdot 2662

. Обратите внимание, что кратные 11 значения

F

встречаются заметно реже, поэтому шестое число уже 850084. Программа печатает шесть строк:

Число	$F$
850018	425007
850019	29282
850023	283338
850040	425018
850062	425029
850084	425040

Ответ: 850018 425007 850019 29282 850023 283338 850040 425018 850062 425029 850084 425040