Выведите все числа, которые являются делителями N и взаимно просты с частным своего деления.

Для данного положительного целого числа N задача состоит в том, чтобы напечатать все числа, скажем, K , такие, что K является делителем N , а K и N / K взаимно просты.

Примеры:

Input: N = 12  
Output: 1 3 4 12  
Explanation:
All numbers K such that it is divisor of N(= 12) and K and N/K are coprime:

1. 1: Since 1 is a divisor of 12 and 1 and 12(= 12/1) are coprime.
2. 3: Since 3 is a divisor of 12 and 3 and 4( = 12/3) are coprime.
3. 4: Since 4 is a divisor of 12 and 4 and 3( = 12/4) are coprime.
4. 12: Since 12 is a divisor of 12 and 12 and 1( = 12/12) are coprime.

Input: N = 100  
Output: 1 4 25 100

Наивный подход: самый простой подход к решению данной проблемы - перебрать диапазон [1, N] и проверить для каждого числа K , является ли K делителем N и НОД K и N/K равно 1 или нет. Если окажется верным , то выведите K . В противном случае проверьте следующий номер.

Временная сложность: O (N * log N)
Вспомогательное пространство: O(1)

Эффективный подход. Приведенный выше подход также можно оптимизировать, используя наблюдение, что все делители представлены парами. Например, если N равно 100 , то все пары делителей: (1, 100), (2, 50), (4, 25), (5, 20), (10, 10) .

Поэтому идея состоит в том, чтобы перебрать диапазон [1, √N] и проверить, выполняются ли оба заданных условия или нет, т. е. является ли какое-либо число K делителем N и НОД K и N/K равно 1 или нет. Если окажется, что это правда , то выведите оба числа. В случае двух равных делителей выведите только один из них.

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

Временная сложность: O(√N*log N)
Вспомогательное пространство: O(1)