Делители

[yestlmush]

Добрый день!

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

[Zealint]

yestlmush в сообщении #612832 писал(а):

Добрый день!

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

Что значит "не очень быстро"? Список делителей Вы быстрее чем за O("количество делителей") не построите. Перебрать же все комбинации степеней простых чисел, входящих в делитель, не так сложно.

Если у Вас не очень быстро, то может проблема в реализации, а не в алгоритме? Надо бы уточнить...

[Sonic86]

Можете хотя бы тут узнать, насколько эта задача сложная.

[Zealint]

Sonic86 в сообщении #612835 писал(а):

Можете хотя бы тут узнать, насколько эта задача сложная.

Она "вычислительно сложная", но не сложная в смысле программирования, это всё-таки разные вещи (или вы опять невнимательно прочитали?). Мне интересно, чего хочет автор, зная, что список делителей будет очень длинным и чего он хочет ускорять.

[yestlmush]

Zealint в сообщении #612834 писал(а):

Что значит "не очень быстро"? Список делителей Вы быстрее чем за O("количество делителей") не построите. Перебрать же все комбинации степеней простых чисел, входящих в делитель, не так сложно.

Если у Вас не очень быстро, то может проблема в реализации, а не в алгоритме? Надо бы уточнить...

Да, но что если мы хотим находить делители множества чисел от 1 до N ? Может быть, можно
использовать что-то типа решета?

[venco]

Чтобы найти простые делители всех чисел до N действительно можно использовать решето (Эратосфена), достаточно только всем составным прописывать не просто флаг "составное" а сам (простой) делитель. А потом из этого массива можно будет быстро находить все простые делители любого числа.