Найдите все делители натурального числа

Опубликовано: 13 Января, 2023

Для заданного натурального числа n выведите все его различные делители.

Примеры:

 Input : n = 10       
 Output: 1 2 5 10

 Input:  n = 100
 Output: 1 2 4 5 10 20 25 50 100

 Input:  n = 125
 Output: 1 5 25 125

Обратите внимание, что эта задача отличается от поиска всех простых множителей.

Наивным решением было бы перебрать все числа от 1 до n, проверить, делится ли это число на n, и распечатать его. Ниже приведена программа для того же:

Выход:

The divisors of 100 are: 
1 2 4 5 10 20 25 50 100

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

Можем ли мы улучшить приведенное выше решение?
Если мы посмотрим внимательно, все делители присутствуют парами. Например, если n = 100, то различные пары делителей: (1,100), (2,50), (4,25), (5,20), (10,10)
Используя этот факт, мы могли значительно ускорить нашу программу.
Мы, однако, должны быть осторожны, если есть два равных делителя, как в случае (10, 10). В таком случае мы напечатаем только один из них.

Ниже приведена реализация для того же самого:

Выход:

The divisors of 100 are: 
1 100 2 50 4 25 5 20 10

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

Однако в решении все еще есть небольшая проблема, вы можете догадаться?
Да! вывод не отсортирован, как мы получили, используя метод грубой силы. Пожалуйста, обратитесь ниже к временному решению O (sqrt (n)), которое печатает делители в отсортированном порядке.
Найти все делители натурального числа | Набор 2
Эта статья предоставлена Ашутош Кумар. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.