Простое число — это целое число больше 1, не имеющее положительных делителей, кроме 1 и самого себя. Найдите наибольший простой делитель числа n. Если n само является простым, верните n.
Реализуйте функцию largest_prime_factor(n).
Ввод
n: Число, для которого нужно найти делитель.
Вывод
Верните его наибольший простой делитель.
Ограничения
2 ≤ n ≤ 10¹². Входное значение 1 исключено, так как у него нет простых делителей.
Примеры
Ввод:
n = 84
Ожидаемый вывод:
expected = 7Ввод:
long long n = 84;
Ожидаемый вывод:
long long expected = 7;Ввод:
long n = 84;
Ожидаемый вывод:
long expected = 7;Пояснение
84 = 2 × 2 × 3 × 7, поэтому наибольший простой делитель — 7.
Ввод:
n = 13
Ожидаемый вывод:
expected = 13Ввод:
long long n = 13;
Ожидаемый вывод:
long long expected = 13;Ввод:
long n = 13;
Ожидаемый вывод:
long expected = 13;Пояснение
13 — простое число, поэтому его наибольший простой делитель — само число 13.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Сначала уберите маленькие простые множители; оставшееся значение может только уменьшаться, и последний множитель будет ответом.
Подсказка 2
Проверяйте делители только до квадратного корня текущего остатка и каждый раз делите его до конца, если он подходит.
Подсказка 3
Если после проверки меньших множителей остаток всё ещё больше 1, значит он прост и это наибольший множитель.
Ожидаемая сложность
время O(√n), доп. память O(1)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.