Минимальные операции по уменьшению 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)

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