Различные простые множители заданного числа N

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

Примеры:

Input: N = 12
Output: 2 3
Explanation: The factors of 12 are 1, 2, 3, 4, 6, 12.
Among these the distinct prime factors are 2 and 3.

Input: N = 39
Output: 3 13

Подход: Подход заключается в использовании карты для проверки того, встречался ли данный фактор числа ранее или нет. Теперь выполните следующие шаги, чтобы решить эту проблему:

1. Создайте посещенную карту, чтобы отслеживать все предыдущие основные факторы.
2. Создайте переменную C и инициализируйте ее значением 2.
3. Пока N делится на C , выведите C , если C не присутствует на карте. Теперь разделите N на C. Также увеличьте C на 1.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: О(N1 ^/2 )

Эффективный подход: этот подход похож на описанный выше подход, в котором мы находим простые факторы. Единственное отличие состоит в том, что мы переходим от 2 к sqrt(n) , чтобы найти все простые множители, поскольку мы знаем, что этого достаточно и для проверки простых чисел. Если число по-прежнему оказывается больше 2, то оно простое, и нам также нужно его напечатать.

Временная сложность: O(N^(1/2))

Вспомогательное пространство: O(N^(1/2))