Арифметическая функция Tau на С++?

Question

[rastr]

Как реализовать алгоритм арифметической функции Tau (кол-во положительных делителей натурального N) на С++ лучше, чем просто перебором чисел от 2 до заданного N / 2? В Википедии про реализацию ничего не сказано и на других сайтах тоже, вроде бы, ничего не находил.

Comments

[Денис Загаевский]

Не до N/2, a до квадратного корня из N

[rastr]

Денис Загаевский, Ну это ведь в случае, если бы я искал простые делители числа N. А так делитель может быть и больше, чем корень из числа, но при этом он не будет превышать N / 2, исключая само собой это же число N.
К примеру, 12: 1^0 + 2^0 + 3^0 + 4^0 + 6^0 + 12^0 = 6. Если бы я искал до корня ответ был бы 4.

[jcmvbkbc]

rastr, каждый делитель Q_i больший квадратного корня из N в точности соответствуют одному делителю q_i меньшему квадратного корня из N, поэтому их можно не искать (Q_i = N / q_j), а просто удвоить число делителей меньших квадратного корня.

К примеру, 12: 1^0 + 2^0 + 3^0 + 4^0 + 6^0 + 12^0 = 6. Если бы я искал до корня ответ был бы 4.

Ответ был бы 3, поскольку sqrt(12) < 4.

[rastr]

jcmvbkbc, А вот еще вопрос, как можно было бы реализовать подобную функцию, только чтобы находила не кол-во, а сумму делителей?

[jcmvbkbc]

чтобы находила не кол-во, а сумму делителей

rastr, складывать найденные делители по мере их нахождения, ммм?

[rastr]

jcmvbkbc, Ну это само собой) Я имею в виду реализовать быстрее, чем просто перебор до N / 2. Как в первой по идеи ведь не выйдет: искать до корня из N.

[jcmvbkbc]

Как в первой по идеи ведь не выйдет: искать до корня из N.

rastr, а если мой комментарий перечитать внимательно и подумать?

[rastr]

jcmvbkbc, А да..всё понял. Спасибо большое за ответ!