Сумма всех простых делителей числа | Набор 2

Опубликовано: 22 Сентября, 2022

По заданному числу N задача состоит в том, чтобы найти сумму всех простых множителей числа N .

Примеры:

Input: 10
Output: 7
Explanation: 2, 5 are prime divisors of 10

Input: 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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ