Здравствуйте, хотел бы спросить у кого есть пример кода алгоритма нахождения делителей с временной сложностью меньше чем O(n)?

Question

Что-то эффективней чем for(let i=1;i<=n;i++) if(n%i==0) res.push(i);

Answer 1

Ну почему же не изменится итерации та станет в 2 раза меньше? А так он бы что-то вычислял бы после n/2 причём в пустую, так как после n/2 только один делитель это n. Вроде алгоритм с использованием факторизации эффективный но понятного разъяснения этого алгоритма я не встречал.

Answer 2

Первое что следует сразу заметить, нет смысла искать делители i>(n/2), т.е. в цикле лучше написать i<=(n/2). Правда от этого алгоритмическая сложность программы не снизится

А вообще, самый большой делитель nmax не превышает n/nmin, можно подумать над условием выхода из цикла заранее, как только известен наименьший делитель nmin