logo标签列表

计算给定数字的约数数量的算法

performancealgorithmpseudocode
183

针对计算给定数字的约数数量，最优算法（在性能上）是什么？

如果您能提供伪代码或示例链接，那将非常好。

编辑：所有答案都非常有帮助，谢谢。 我正在实现Atkin筛法，然后将使用类似于Jonathan Leffler指出的方法。 Justin Bozonier发布的链接提供了我所需的更多信息。

根据您的要求，得出因子数量是含糊不清的。我猜您想要的是非唯一质因数的数量，因为如果您不需要这个，我可以编写一个程序，始终返回1（如果要分解的数字为1）或2（如果要分解的数字为其他任何数字）。0可能需要更改... - Justin Bozonier
@sker：你需要计算哪个数值范围内的因子？有很多种计算因子的方法，每种方法都更适合特定的范围。 - Ande Turner
2
这里有一个相关的有趣问题：http://projecteuler.net/problem=12 - daniloquio
1
即使来自编辑后的维基百科文章的天真阿特金筛法在巨大且不切实际的限制下也永远不会比最大化车轮分解的厄拉托色尼筛法更快，并且页面分段版本甚至更加支持SoE（请参见Atkin的合作者Bernstein实施的SoE primesieve与SoA primegen的SoA）常见的不正确的互联网知识是，他们的研究证明了SoA更快，但他们人为地限制了用于证明这一点的SoE的优化。 有关进一步说明，请参见我的SoA答案。 - GordonBGood
26个回答
77

Dmitriy说你需要使用Atkin筛法生成质数列表，但我不认为这可以解决所有问题。现在你有了一个质数列表，你需要看看其中有多少质数作为因子（以及出现次数）。

这里是该算法的Python代码，在这里搜索“Subject: math - need divisors algorithm”。然后只需计算列表中的项目数量而不是返回它们即可。

这是Dr. Math的解释，讲述了您需要在数学上做什么。

基本上，如果您的数字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%确定，但如果不是这样，那么也是类似的。

1
如果你要分解一个大数，你甚至不想看素数列表。你希望尽快消除整个范围的可能性！请参见我的答案。 - user11318
@jb 网络连接失败了。我现在没有它。很抱歉。:( - Justin Bozonier
2
所以 n = (a^x * b^y * c^z)-(x + 1) * (y + 1) * (z + 1) 是规则。 - SIslam
1
正如@Shashank所说，“EDIT:”部分的算法是错误的：假设n = 45 = 3 * 3 * 5。最大的质因数是5，但将其乘以自身直到超过n会导致算法报告它有2个因子5的副本（因为5 * 5 = 25 <45）。 - j_random_hacker
1
“阿特金筛法”在最佳情况下的运行时间复杂度为**O(N / log(log(N)))。而暴力检查从1到Sqrt(n)的所有可能除数的运行时间复杂度为O(Sqrt(N))**，这远远优于前者。为什么这个答案被接受了呢？ - le_m
显示剩余2条评论
48
有比Atkin筛法更多的因数分解技巧。例如，假设我们想要分解5893。它的平方根是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位数，例如124321342332143213122323434312213424231341。（如果您想知道它的因式分解，它是29*439*1321*157907*284749*33843676813*4857795469949。我非常有信心它没有使用Atkin筛法来计算...）
1
你的技巧很聪明，但是它没有告诉我这个数有多少因子，对吗？ - sker
23
一旦你得到了质因数分解，确定有多少个因数就很简单了。假设质因数是p1, p2, ..., pk，并且它们重复出现m1, m2, ..., mk次。那么因数的数量就是(1+m1)(1+m2)...(1+mk)。 - user11318
一个有趣的筛法是二次筛法。它使用了数论中的二次同余和一些线性代数知识。我学习了足够的知识，在大学的第二年数论课程中使用它。 - Tanner
35

@Yasky

你的约数函数存在一个错误，对于完全平方数无法正确工作。

尝试使用以下代码：

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

    if (x == 1) return 1;

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

    return numberOfDivisors;
}
6
当i = 0时，Won't (x % i)导致除以零错误吗？应该将i的范围设为1..limit吗？ - rhu
@rhu 检查0毫无意义，因为0不是任何数字的因数。 - EJoshuaS - Stand with Ukraine
30

我不同意使用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)

提示 这是可解决此问题的Python代码。

15

这是一个直截了当的O(sqrt(n))算法。我用它来解决欧拉计划

def divisors(n):
    count = 2  # accounts for 'n' and '1'
    i = 2
    while i ** 2 < n:
        if n % i == 0:
            count += 2
        i += 1
    if i ** 2 == n:
        count += 1
    return count
但是你为什么总是将计数增加2？...你应用了什么定理吗？ - SummerCode
3
因为你只需要枚举到sqrt(n)就可以了。例如：如果你要找36的所有因数，只需要从2枚举到6。你知道1和36、2和18、3和12、4和9以及6是所有的因数，并且它们都是成对出现的。 - Antony Thomas
2
非常感谢你 Anthony，我现在明白了:D！一个小补充：我认为应该将sqrt(n)值单独处理，因为目前它考虑了两次而不是一次，我认为。 - SummerCode
虽然O(sqrt(n))并不算太糟糕，但它并不是最优的。计算质因数分解可以更快地完成，并足以计算出除数的数量。 - le_m
在每次迭代中，您必须计算i²，将i与√n（仅计算一次）进行比较是否更快？ - Yukulélé
11

这个有趣的问题比看起来要难得多，而且还没有得到解答。这个问题可以分解为两个非常不同的问题。

1 给定N，找出N的质因数列表L

2 给定L，计算唯一组合的数量

现在看到的所有答案都涉及＃1，并未提到对于巨大的数字它是不可行的。 对于适度大小的N，即使是64位数字，也很容易；但对于巨大的N，质因数分解问题可能需要“永远”。 公钥加密取决于此。

问题＃2需要更多讨论。 如果L仅包含唯一数字，则使用组合公式选择n项中的k个对象进行简单计算。 实际上，您需要在变化k从1到sizeof（L）时对应用公式的结果求和。 但是，L通常将包含多个重复的质数。 例如，L = {2,2,2,3,3,5}是N = 360的分解。 现在这个问题就相当困难了！

重新陈述＃2，给定包含k个项目的集合C，其中项目a具有a'个副本，项目b具有b'个副本等，有多少个1到k-1个项目的唯一组合？ 例如，如果L = {2,2,2,3,3,5}，则必须每个独特的子集合-{2}，{2,2}，{2,2,2}，{2,3}，{2,2,3,3}都仅出现一次。 每个这样的唯一子集都是通过将子集中的项相乘而得到N的唯一除数。

这里有一个链接，其中包含一个非常类似于2的问题的伪代码。http://answers.google.com/answers/threadview/id/392914.html - mR_fr0g
5
问题#2有一个众所周知的解决方案。对于{p_i，k_i}的因数分解，其中p_i是一个具有k_i重复次数的数的质因子，该数的总因数个数为(k_1+1)*(k_2+1)*...*(k_n+1)。我猜你现在已经知道这个了，但我写下来是为了让随机读者受益。 - Will Ness
10
7

只需一行代码
我仔细思考了你的问题，并尝试编写了一段高效且性能良好的代码，
要在屏幕上打印给定数字的所有约数，我们只需要一行代码！（使用gcc编译时选项-std=c99）

for(int i=1,n=9;((!(n%i)) && printf("%d is a divisor of %d\n",i,n)) || i<=(n/2);i++);//n is your number

要找到一个数的约数个数，您可以使用以下非常快速的函数（对于除1和2之外的所有整数数字均有效）：

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return counter;
}

如果您将给定的数字视为除数（对于所有整数数字，除了1和2），则可以正确地处理。

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    return ++counter;
}

注意：上述两个函数对于除了数字1和2之外的所有正整数都能正确工作， 因此它适用于所有大于2的数字。 但如果您需要覆盖1和2，可以使用以下其中一个函数（速度稍慢）

int number_of_divisors(int n)
{
    int counter,i;
    for(counter=0,i=1;(!(n%i) && (counter++)) || i<=(n/2);i++);
    if (n==2 || n==1)
    {
    return counter;
    }
    return ++counter;
}

或者

int number_of_divisors(int n)
{
    int counter,i;
for(counter=0,i=1;(!(i==n) && !(n%i) && (counter++)) || i<=(n/2);i++);
    return ++counter;
}

small is beautiful :)

6
你可以试试这个方法。它有点巧妙，但速度相对较快。
def factors(n):
    for x in xrange(2,n):
        if n%x == 0:
            return (x,) + factors(n/x)
    return (n,1)
2
虽然这个函数可以在合理的时间内提供n的质因数分解，但是它a)不是最优的，b)也不能像OP的问题那样计算给定数字的除数数量。 - le_m
由于递归，它不适用于大数字。 - whackamadoodle3000
虽然这不是最优的方法，而且它实际上是列出因子而不是计算它们，但其简单和美妙令人惊叹，并且速度相当快。^^ - Gaurav Singhal
6
Atkin筛法是Eratosthenes筛法的优化版本，可找出给定整数以下的所有质数。您可以通过谷歌搜索了解更多详细信息。
一旦您拥有了该列表，将数字除以每个质数以查看它是否是一个确切的除数（即余数为零）就很简单了。
计算数字n的除数的基本步骤如下（这是从实际代码转换过来的伪代码，因此希望我没有引入错误）：
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
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接