计算给定数的除数的算法 [英] Algorithm to calculate the number of divisors of a given number

问题描述

计算给定数字的除数的最佳算法(性能方面)是什么?

What would be the most optimal algorithm (performance-wise) to calculate the number of divisors of a given number?

如果您能提供伪代码或某个示例的链接，那就太好了.

It'll be great if you could provide pseudocode or a link to some example.

所有的答案都非常有帮助，谢谢.我正在实施阿特金筛分法，然后我将使用类似于乔纳森莱夫勒指出的东西.Justin Bozonier 发布的链接包含有关我想要的内容的更多信息.

All the answers have been very helpful, thank you. I'm implementing the Sieve of Atkin and then I'm going to use something similar to what Jonathan Leffler indicated. The link posted by Justin Bozonier has further information on what I wanted.

推荐答案

Dmitriy 是对的，您希望阿特金筛网生成素数列表，但我认为这并不能解决整个问题.既然您有一个质数列表，您就需要查看这些质数中有多少个作为除数(以及频率).

Dmitriy is right that you'll want the Sieve of Atkin to generate the prime list but I don't believe that takes care of the whole issue. Now that you have a list of primes you'll need to see how many of those primes act as a divisor (and how often).

这里有一些用于算法的 python 看这里并搜索主题:数学 - 需要除数算法".只需计算列表中项目的数量，而不是返回它们.

Here's some python for the algo Look here and search for "Subject: math - need divisors algorithm". Just count the number of items in the list instead of returning them however.

这是一位数学博士，它解释了您到底需要什么数学上做.

Here's a Dr. Math that explains what exactly it is you need to do mathematically.

基本上归结为如果您的号码 n 是:
n = a^x * b^y * c^z
(其中 a、b 和 c 是 n 的质数除数，x、y 和 z 是除数重复的次数)那么所有除数的总数是:
(x + 1) * (y + 1) * (z + 1).

Essentially it boils down to if your number n is:
n = a^x * b^y * c^z
(where a, b, and c are n's prime divisors and x, y, and z are the number of times that divisor is repeated) then the total count for all of the divisors is:
(x + 1) * (y + 1) * (z + 1).

顺便说一句，如果我正确理解了这一点，要找到 a、b、c 等，您将想要做相当于贪婪算法的事情.从最大的质数除数开始，然后自乘，直到进一步的乘法超过数字 n.然后移动到下一个最低因子，乘以前一个素数 ^ 乘以当前素数的次数，并继续乘以该素数，直到下一个将超过 n... 等等.跟踪您乘以该素数的次数将除数加在一起并将这些数字应用到上面的公式中.

BTW, to find a,b,c,etc you'll want to do what amounts to a greedy algo if I'm understanding this correctly. Start with your largest prime divisor and multiply it by itself until a further multiplication would exceed the number n. Then move to the next lowest factor and times the previous prime ^ number of times it was multiplied by the current prime and keep multiplying by the prime until the next will exceed n... etc. Keep track of the number of times you multiply the divisors together and apply those numbers into the formula above.

对我的算法描述不是 100% 确定，但如果不是，那就是类似的东西.

Not 100% sure about my algo description but if that isn't it it's something similar .

这篇关于计算给定数的除数的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！