Сумма всех простых делителей числа | Набор 2
Опубликовано: 22 Сентября, 2022
По заданному числу N задача состоит в том, чтобы найти сумму всех простых множителей числа N .
Примеры:
Input: 10
Output: 7
Explanation: 2, 5 are prime divisors of 10Input: 20
Output: 7
Explanation: 2, 5 are prime divisors of 20
Подход: Эту задачу можно решить, найдя все простые множители числа. Выполните следующие шаги, чтобы решить эту проблему:
- Инициализируйте переменную sum как 0 , чтобы сохранить сумму простых делителей N.
- Если N делится на 2, прибавьте 2 к сумме и разделите N на 2 , пока оно не станет делиться.
- Выполните итерацию в диапазоне [3, sqrt(N)] , используя переменную i с шагом 2 :
- Если N делится на i, прибавьте i к сумме и разделите N на i , пока оно не станет делиться.
- Если N — простое число больше 2, добавьте N к сумме.
- После выполнения вышеуказанных шагов выведите сумму в качестве ответа.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(sqrt(N))
Вспомогательное пространство: O(1)