Как подсчитать кол-во делителей?

Question

[Firetheestle]

Как можно подсчитать кол-во делителей при делении числа на число? язык Си

Answer 1

[Mrrl]

Кладём в аккумулятор 1.
Перебираем числа от 2. Если есть возможность - то только простые, или 2 и нечётные...
Если наше число x делится на текущее число p, то делим его, пока делится, считаем, сколько раз разделилось (значит, x делился на p^n). Умножаем аккумулятор на n+1.
Если дошли до такого p, что p^2 > x, то смотрим: если x не равен 1, умножаем аккумулятор на 2.

Например:
x=5040, acc=1
p=2. x делится на 2^4. После деления x=315, acc=5.
p=3. x делится на 3^2. После деления x=35, acc=5*3=15.
p=5. x делится на 5^1, После деления x=7, acc=15*2=30.
p=6. x < p^2, выходим из цикла
x!=1 => acc=30*2=60.
Ответ: 60 делителей.

Если это слишком медленно - изучайте быстрые алгоритмы факторизации.

Answer 2

[Иван]

1 ?

Answer 3

[Владимир Мартьянов]

А в чем именно сложность-то?

Comments

[abs0lut]

В лени, очевидно

Answer 4

[Виктор Паперно]

Алгоритм крайне простой :

Идём от 1 до корня из числа(оптимальное решение) или до половины числа (нормальное решение)
и проверяем, чему равен остаток от деления исходного числа на данное. Если остаток равен нулю, то
увеличваем число делителей на один.