Как в ЕГЭ · 16 из 20
№25. Ровно столько делителей
По мотивам задания №25, второй его вид. На отрезке чисел нужно найти те, у которых ровно k делителей, не считая единицы и самого числа, — и у каждого назвать наибольший из них. Числа на экзамене — сотни тысяч и миллионы, и перебирать делители до самого числа слишком долго: хватает до корня.
Что сделать
Найдите числа отрезка, у которых ровно k делителей, кроме 1 и самого числа, — с наибольшим из этих делителей.
Что приходит
aиb— концы отрезка, оба включительно, натуральные, до 10¹⁰k— сколько делителей нужно, от 1
Что вернуть
Список пар (число, наибольший делитель) по возрастанию; если таких нет — пустой.
Допишите функцию rovno_deliteley в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
На отрезке от 10 до 16 при k = 2: у 10 делители 2 и 5 — подходит, наибольший 5; у 14 — 2 и 7; у 15 — 3 и 5. У 12 их четыре (2, 3, 4, 6), у 16 — три (2, 4, 8). Ответ [(10, 5), (14, 7), (15, 5)].
rovno_deliteley(10, 16, 2)
[(10, 5), (14, 7), (15, 5)]
Делители числа n — натуральные d, на которые n делится без остатка; 1 и само n не считаются. Каждый делитель — один раз: у 49 делитель один — 7. Отрезок — до тысячи чисел, сами числа — до 10¹⁰: перебор делителей до самого числа не успевает, до корня из него — успевает.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.