Минимальные операции по уменьшению N до простого числа путем вычитания с его наибольшим делителем
Опубликовано: 21 Сентября, 2022
Дано положительное целое число N . В одной операции вычтите N с его наибольшим делителем, отличным от N и 1 . Задача состоит в том, чтобы найти минимум операций, необходимых для сведения N точно к простому числу.
Примеры:
Input: N = 38
Output: 1
Explanation: Highest divisor of 38 is 19, so subtract it (38 – 19) = 19. 19 is a prime number.
So, number of operations required = 1.Input: N = 69
Output: 2
Подход: Эту проблему можно решить, используя простые понятия математики. Выполните следующие шаги, чтобы решить данную проблему.
- Сначала проверьте, является ли N уже простым числом.
- Если N уже является простым числом, вернуть 0 .
- В противном случае инициализируйте переменную, скажем, count = 0 , чтобы сохранить количество необходимых операций.
- Инициализируйте переменную, скажем, i=2, и запустите цикл while до N!=i
- Запустите цикл while и на каждой итерации вычтите текущее значение N из его наибольшего делителя.
- Вычислите шаги и увеличьте количество на 1 .
- Верните счет .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(sqrtN)
Вспомогательное пространство: O(1)