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

如果我们可以提供伪代码或者一些示例的链接，那就太好了。

编辑：所有的答案都非常有帮助，谢谢。我正在实施Atkin筛分法，然后将使用类似于Jonathan Leffler所指出的方法。贾斯汀·博佐尼尔(Justin Bozonier)发布的链接提供了有关我想要的更多信息。

解决方案

我们需要此处描述的Atkin筛子：http://en.wikipedia.org/wiki/Sieve_of_Atkin

这不只是将数字分解为因子决定所有数字因子的问题吗？然后，我们可以决定是否需要一个或者多个因素的所有组合。

因此，一种可能的算法是：

factor(N)
    divisor = first_prime
    list_of_factors = { 1 }
    while (N > 1)
        while (N % divisor == 0)
            add divisor to list_of_factors
            N /= divisor
        divisor = next_prime
    return list_of_factors

然后由我们来组合因素以确定其余的答案。

德米特里(Dmitriy)是对的，我们希望让《阿特金筛子》(Sieve of Atkin)生成主要清单，但我不认为这可以解决整个问题。现在我们已经有了素数的列表，我们将需要查看其中有多少素数可以用作除数(以及除数)。

这是用于算法的一些python。请在此处搜索"主题：数学需要除数算法"。只需计算列表中的项目数即可，而不是返回它们。

这是一位数学博士，解释了我们需要做的确切的数学运算。

本质上可以归结为数字n是否为：
n = a ^ x * b ^ y * c ^ z`

(其中a，b和c是n的素数除数，x，y和z是除数重复的次数)
那么所有除数的总数为：
(x + 1)*(y + 1)*(z + 1)。

编辑：顺便说一句，要找到a，b，c等，如果我正确理解的话，我们将想做一个相当于贪婪算法的事情。从最大的素数除数开始，并将其自身相乘，直到进一步的乘积超过数字n。然后移至下一个最低因子，并乘以上一个质数^乘以当前质数的次数，并继续乘以质数，直到下一个质数超过n ...等。除数并将这些数字应用到上面的公式中。

并非100％知道我的算法描述，但如果不是，那是类似的事情。

• 创建一个素数表以查找所有小于或者等于数字平方根的素数(就我个人而言，我将使用Atkin筛分法)
• 计算所有小于或者等于数字平方根的素数，然后将其乘以2. 如果数字的平方根是整数，则从计数变量中减去1.

我不知道MOST有效的方法，但我会执行以下操作：

应该工作\ o /

如果需要的话，我明天可以在C语言中编写代码进行演示。

阿特金(Atkin)筛是Eratosthenes筛的优化版本，它给出所有质数直至给定的整数。我们应该可以在Google上搜索更多详细信息。

有了该列表后，只需将数字除以每个质数就可以了，这很简单，以查看它是否是一个精确的除数(即，余数为零)。

for z in 1..n:
    prime[z] = false
prime[2] = true;
prime[3] = true;

for x in 1..sqrt(n):
    xx = x * x

    for y in 1..sqrt(n):
        yy = y * y

        z = 4*xx+yy
        if (z <= n) and ((z mod 12 == 1) or (z mod 12 == 5)):
            prime[z] = not prime[z]

        z = z-xx
        if (z <= n) and (z mod 12 == 7):
            prime[z] = not prime[z]

        z = z-yy-yy
        if (z <= n) and (x > y) and (z mod 12 == 11):
            prime[z] = not prime[z]

for z in 5..sqrt(n):
    if prime[z]:
        zz = z*z
        x = zz
        while x <= limit:
            prime[x] = false
            x = x + zz

for z in 2,3,5..n:
    if prime[z]:
        if n modulo z == 0 then print z

计算一个数(n)除数的基本步骤是[这是从实码转换成的伪码，所以希望我没有引入错误]：

除Atkin的筛子外，还有更多的分解技术。例如，假设我们要分解5893. 那么它的sqrt是76.76 ...现在，我们将尝试将5893写成平方的乘积。那么(77 * 77 5893)= 36的平方是6，所以5893 = 77 * 77 6 * 6 =(77 + 6)(77-6)= 83 * 71. 如果那没有用，我们将研究78 * 78 5893是否是一个完美的正方形。等等。使用这种技术，我们可以比测试单个素数更快地快速测试n的平方根附近的因子。如果我们将此技术与筛网结合使用，可以排除较大的质数，那么与单独筛网相比，我们将拥有更好的分解方法。

这只是已开发的众多技术中的一种。这是一个相当简单的过程。例如，要花很多时间学习足够的数论，才能理解基于椭圆曲线的因式分解技术。 (我知道它们存在。我不理解它们。)

因此，除非我们要处理小整数，否则我不会尝试自己解决该问题。相反，我会尝试找到一种方法来使用PARI库之类的方法，该方法已经实现了高效的解决方案。这样，我可以在大约0.05秒内分解出一个随机的40位数，例如124321342332143143213122323434312213424231341. (如果我们想知道，它的因式分解是29 * 439 * 1321 * 157907 * 284749 * 33843676813 * 4857795469949. 我非常有信心它没有使用Atkin的筛子解决这个问题。)

• 概述：http://en.wikipedia.org/wiki/Divisor_function
• 小n的值和一些有用的参考：AOOOOO5：d(n)(也称为tau(n)或者sigma_0(n))，n的除数。
• 实际示例：整数分解

我们问题的答案在很大程度上取决于整数的大小。小数的方法，例如少于100位，而对于〜1000位的数字(例如用于密码学)则完全不同。

我不同意Atkin的筛分方法，因为检查[1，n]中的每个数字是否为素数比将其除以除法要容易得多。

import operator
# A slightly efficient superset of primes.
def PrimesPlus():
  yield 2
  yield 3
  i = 5
  while True:
    yield i
    if i % 6 == 1:
      i += 2
    i += 2
# Returns a dict d with n = product p ^ d[p]
def GetPrimeDecomp(n):
  d = {}
  primes = PrimesPlus()
  for p in primes:
    while n % p == 0:
      n /= p
      d[p] = d.setdefault(p, 0) + 1
    if n == 1:
      return d
def NumberOfDivisors(n):
  d = GetPrimeDecomp(n)
  powers_plus = map(lambda x: x+1, d.values())
  return reduce(operator.mul, powers_plus, 1)

这里的一些代码虽然稍微有些hacker，但是通常要快得多：

ps这是解决这个问题的有效python代码。

这个有趣的问题比看起来要难得多，并且尚未得到回答。该问题可以分解为2个非常不同的问题。

到目前为止，我看到的所有答案都是针对＃1的，而更不用说它对于大量用户而言并非易事。对于中等大小的N甚至64位数字，这很容易；对于巨大的N，保理问题可能会"永远存在"。公钥加密与此有关。

问题2需要更多讨论。如果L仅包含唯一数字，则使用从n个项目中选择k个对象的组合公式进行简单计算。实际上，我们需要在将k从1更改为sizeof(L)时，对应用公式的结果求和。但是，L通常包含多个素数的多次出现。例如，L = {2,2,2,3,3,5}是N = 360的因式分解。现在这个问题相当困难！

在给定集合C包含k个项目的情况下重述＃2，使得项目a具有a'重复项，项目b具有b'重复项，等等。有1到k-1个项目的多少个唯一组合？例如，{2}，{2,2}，{2,2,2}，{2,3}，{2,2,3,3}必须分别出现一次，并且仅在L = {2,2 ，2,3,3,5}。通过将子集合中的项目相乘，每个此类唯一子集合都是N的唯一除数。

def factors(n):
    for x in xrange(2,n):
        if n%x == 0:
            return (x,) + factors(n/x)
    return (n,1)

我们可以尝试这个。有点破烂，但速度相当快。

在提交解决方案之前，请考虑在典型情况下，Sieve方法可能不是一个好的答案。

前一段时间有一个素数问题，我进行了时间测试-对于32位整数，至少确定它是否素数比强力慢。发生两个因素：

1)尽管人们花了一些时间进行除法，但他们在计算机上的速度非常快-类似于查找答案的成本。

2)如果没有主表，则可以创建一个完全在L1缓存中运行的循环。这使其速度更快。

一旦有了素数分解，便可以找到除数的数量。在每个因子上对每个指数加一个，然后将指数相乘。

例如：
36
素数分解：2 ^ 2 * 3 ^ 2
除数：1，2，3，4，4，9，9，12，18，36
除数的数量：9

给每个指数加2 ^ 3 * 3 ^ 3
乘以指数：3 * 3 = 9

int divisors (int x) {
    int limit = x;
    int numberOfDivisors = 1;

    for (int i(0); i < limit; ++i) {
        if (x % i == 0) {
            limit = x / i;
            numberOfDivisors++;
        }
    }

    return numberOfDivisors * 2;
}

除数做得很壮观：它们完全分开。如果要检查数字n的除数，显然跨越整个频谱1 ... n是多余的。我没有对此做任何深入的研究，但是我解决了三角数上的Euler项目问题​​12. 我针对大于500的除数测试的解决方案运行了309504微秒(〜0.3s)。我为解决方案编写了这个除数函数。

对于每种算法，都有一个弱点。我认为这对素数来说是微弱的。但是由于三角数字没有打印出来，因此可以完美地实现其目的。从我的分析来看，我认为它做得很好。

段落数量不匹配