Задание 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 — Проверка делимости

Напишите программу, которая перебирает целые числа, большие 450000, в порядке возрастания и ищет среди них такие, для которых наибольший натуральный делитель, не равный самому числу, не является простым числом. Программа должна найти и вывести первые 6 таких чисел и соответствующие им значения упомянутых делителей. Формат вывода: для каждого из 6 таких найденных чисел в отдельной строке сначала выводится само число, затем упомянутый делитель. Строки выводятся в порядке возрастания найденных чисел.
Например, для числа 105 наибольший натуральный делитель 35 не является простым, для числа 15 наибольший натуральный делитель 5 — простое число, а для числа 13 такого делителя не существует.

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

450002 225001 450004 225002 450006 225003 450007 26471 450008 225004 450009 150003

Пояснение

Решение:

Наибольший делитель числа $n$ , не равный самому $n$ , — это $n/p$ , где $p$ — наименьший простой делитель $n$ . Поэтому достаточно найти $p$ перебором $d$ от 2 до $\sqrt{n}$ , а затем проверить, простое ли частное $n/p$ .

Простые числа сразу отбрасываем: по условию для них такого делителя не существует. Заметим, что оставшееся условие равносильно тому, что число $n$ раскладывается минимум на три простых множителя с учётом кратности: если множителей всего два, то $n = p\cdot q$ и частное $n/p = q$ простое.

def is_prime(x):
    if x < 2:
        return False
    d = 2
    while d * d <= x:
        if x % d == 0:
            return False
        d += 1
    return True

def big_div(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return n // d      # наибольший делитель, не равный n
        d += 1
    return 0                   # n простое: такого делителя нет

n = 450000
found = 0
while found < 6:
    n += 1
    d = big_div(n)
    if d != 0 and not is_prime(d):
        print(n, d)
        found += 1

Программа выводит:

450002 225001
450004 225002
450006 225003
450007 26471
450008 225004
450009 150003

Ответ: 450002 225001 450004 225002 450006 225003 450007 26471 450008 225004 450009 150003