计算给定数量的除数数的算法

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

如果您能提供伪代码或链接到一些示例,那将会很棒.

编辑:所有答案都非常有帮助,谢谢.我正在实施Atkin的Sieve,然后我将使用类似于Jonathan Leffler所说的东西.Justin Bozonier发布的链接提供了我想要的更多信息.

1> Justin Bozon..：

---

德米特里是对的,你会希望阿特金的筛子产生最佳清单,但我不认为这会解决整个问题.既然你有一个素数列表,你需要看看有多少素数作为除数(以及多久).

这里是algo的一些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%肯定我的算法描述,但如果不是它,它是类似的东西.

---

所以`n =(a ^ x*b ^ y*c ^ z) - (x + 1)*(y + 1)*(z + 1)`是规则

2> user11318..：

---

除了阿特金的筛子,还有很多分解技术.例如,假设我们想要因子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库.有了它,我可以在大约.05秒内计算一个随机的40位数字,如124321342332143213122323434312213424231341.(如果你想知道的话,它的因子分解是29*439*1321*157907*284749*33843676813*4857795469949.我非常有信心,它没有用阿特金的筛子来解决这个问题......)

---

一旦你进行了素数分解,找出有多少因素是很简单的.假设素因子是p1,p2,...,pk,它们重复m1,m2,...,mk次.然后有(1 + m1)(1 + m2)......(1 + mk)因子.

3> 小智..：

---

@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;
}

---

当i = 0时,不会(x%i)导致除以零？我应该= 1..limit？

4> Tyler..：

---

我不同意阿特金的筛子是要走的路,因为它可能很容易花费更长的时间来检查[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)

ps这是解决这个问题的工作python代码.

5> dongilmore..：

---

这个有趣的问题比它看起来要难得多,而且还没有得到回答.这个问题可以归结为两个截然不同的问题.

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,给定集合C包含k个项目,使得项目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的唯一除数.

---

问题#2有一个众所周知的解决方案.对于{p_i,k_i}的因式分解,其中`p_i`是具有`k_i'多重性的数的素因子,该数的除数总数为`(k_1 + 1)*(k_2 + 1)*..*(k_n + 1)`.我想你现在知道了这一点,但是如果这里有一个随机的读者,我会把它写下来.

6> jfs..：

---

您的问题的答案在很大程度上取决于整数的大小.小数字(例如,小于100位)和数字~1000位(例如在密码学中使用)的方法是完全不同的.

概述:http://en.wikipedia.org/wiki/Divisor_function

小的n和一些有用的参考值:AOOOOO5:d(n)(也称为tau(n)或sigma_0(n)),n的除数.

现实世界的例子:整数分解

7> Antony Thoma..：

---

这是一个直接的O(sqrt(n))算法.我用它来解决项目euler

def divisors(n):
    count=2 # accounts for 'n' and '1'
    i=2
    while(i**2 < n):
        if(n%i==0):
            count+=2
        i+=1
    count+=(1 if i**2==n else 0)
    return count  

---

因为你只是在直到sqrt(n).例如:如果你试图找到36的所有除数 - 你将从2到6计数.你知道1&36,2和18,3和12,4和9,6,6都是除数,它们成对出现.

---

非常感谢安东尼,我现在明白了:D!一个小小的附录:我认为它应该单独处理sqrt(n)值,因为现在它需要考虑两次而不是一次,我认为

8> هومن جاویدپو..：

---

只有一行
我对你的问题非常谨慎,我试着编写一个高效且高性能的代码.要在屏幕上打印给定数字的所有除数,我们只需要一行代码!(通过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;
}

小很漂亮:)

9> paxdiablo..：

---

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

10> Michael..：

---

你可以试试这个.它有点hackish,但速度相当快.

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

---

虽然这个函数在合理的时间内提供n的素因子分解,但它是a)不是最优的而b)根据OP的问题不计算给定数的除数的数量

11> 小智..：

---

一旦你进行了素数分解,就有办法找到除数的数量.在每个单独的因子上为每个指数添加一个,然后将指数相乘.

例如:36素因子分解:2 ^ 2*3 ^ 2除数:1,2,3,4,6,9,12,18,36除数数:9

为每个指数加1 ^ 3*3 ^ 3乘以指数:3*3 = 9