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个回答
5
一旦你有了质因数分解，就可以找到因数的数量。在每个单独的因子上将指数加一，然后将指数相乘。
例如： 36 质因数分解：2^2*3^2 因数：1、2、3、4、6、9、12、18、36 因数的数量：9
将每个指数加一 2^3*3^3 将指数相乘：3*3 = 9
4

这是一个高效的解决方案：

#include <iostream>
int main() {
  int num = 20; 
  int numberOfDivisors = 1;

  for (int i = 2; i <= num; i++)
  {
    int exponent = 0;
    while (num % i == 0) {
        exponent++; 
        num /= i;
    }   
    numberOfDivisors *= (exponent+1);
  }

  std::cout << numberOfDivisors << std::endl;
  return 0;
}
4
在你决定解决方案之前，请考虑筛选法可能不是典型情况下的好答案。不久前，有一个主要问题，我进行了一次时间测试 - 对于32位整数，至少确定它是否为质数比暴力更慢。这里有两个因素：
1）尽管人类需要一段时间才能进行除法，但计算机上很快 - 类似于查找答案的成本。
2）如果没有质数表，您可以制作一个仅在L1缓存中运行的循环。这使得它更快。
2

这是计算一个数的因子最基本的方法：

class PrintDivisors
{
    public static void main(String args[])
    {

    System.out.println("Enter the number");

    // Create Scanner object for taking input
    Scanner s=new Scanner(System.in);

    // Read an int
    int n=s.nextInt();

        // Loop from 1 to 'n'
        for(int i=1;i<=n;i++)
        {

            // If remainder is 0 when 'n' is divided by 'i',
            if(n%i==0)
            {
            System.out.print(i+", ");
            }
        }

    // Print [not necessary]    
    System.out.print("are divisors of "+n);

    }
}
2
数论教材称除数计数函数为tau。第一个有趣的事实是它是乘性的，即当a和b没有公共因子时，τ(ab) = τ(a)τ(b)。（证明：a和b的每对除数都会得到ab的一个不同的除数）。
现在请注意，对于一个质数p，τ(p**k) = k+1 （p的幂）。因此您可以从其分解轻松计算出τ(n) 。
然而，分解大数字可能很慢（RSA密码学的安全性取决于两个大质数的乘积难以分解）。这就建议使用此优化算法：
  1. 测试数字是否为素数（快速）
  2. 如果是，则返回2
  3. 否则，分解数字（如果有多个大质因子，则较慢）
  4. 从分解中计算τ(n)
2
1
这将为您提供给定数字以下的质数 - 但不能保证这些质数将成为除数？（除非我漏掉了什么） - Andrew Edgecombe
从这里到找出所有小于sqrt(N)的能够整除N的质数只需要一个快速的跳跃。 - SquareCog
1
可能是一个快速的跳跃，但是测试所有小于sqrt（N）的质数仍然是一种不好的因式分解技术，无论你如何高效地找到它们。有很多方法可以改进这个问题。 - user11318
测试质数的时间复杂度为O(N)，而查找质数才是难点。但即使使用未经优化的欧拉筛法，您仍然可以在不到一秒钟的时间内找到几百万以下的所有质数。这涵盖了任何64位数字，我相信我们并不谈论加密级别的因式分解。 - Matthew Scharley
2
除数有一个惊人的特点：它们可以完全分割。如果您想检查数字n的除数数量，那么显然无需跨越整个范围1...n。我没有进行任何深入研究，但我解决了欧拉计划中三角形数问题12。我为解决方案编写了这个除数函数，用于进行大于500个除数的测试，运行时间为309504微秒（约0.3秒）。请参考以下代码：
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;
}

每个算法都有弱点。我曾认为它对质数不利，但由于三角形数不是质数，这个算法毫无瑕疵地发挥了作用。从我的剖析结果来看，我认为它表现得非常好。

节日快乐。

1
在这里的第一次迭代中，您将会遇到除以0的情况。 - barfoon
不幸的是，++i与i++不同（后者会导致除以零错误）。 - Igbanam
我用PHP编写了你的函数并运行它 - 这是我的结果 - http://i.minus.com/iKzuSXesAkpbp.png - barfoon
由于某种奇怪的原因，这对我来说完美无缺。哦，我的错。将“numberOfDivisors”和迭代器从1开始；这应该可以消除除以零的错误。 - Igbanam
1
你的算法对于完全平方数不起作用。例如，对于输入x = 4，它返回4，因为它将2计算了两次...1、2、2、4。正确答案应该是3：1、2、4。 - Michael
@michael 只有在我们寻找独特解决方案时才需要。2 x 2 是 4 的因子组合...所以当然，它返回比完全需要的因子多 1 个，但如果我们只是寻找因子而不是独特因子，它仍然可以正常工作。 - Alexandre
1
这是我写的一个函数。它的最坏时间复杂度为O(sqrt(n)),而最好的情况则为O(log(n))。它会给出所有素数因子及其出现次数。
public static List<Integer> divisors(n) {   
    ArrayList<Integer> aList = new ArrayList();
    int top_count = (int) Math.round(Math.sqrt(n));
    int new_n = n;

    for (int i = 2; i <= top_count; i++) {
        if (new_n == (new_n / i) * i) {
            aList.add(i);
            new_n = new_n / i;
            top_count = (int) Math.round(Math.sqrt(new_n));
            i = 1;
        }
    }
    aList.add(new_n);
    return aList;
}
我不知道这个函数计算的是什么，但它绝对不是n的因数列表。 - le_m
1

质数筛法在这里非常明确。 P[] 是一个质数列表，其中包含小于等于 sq = sqrt(n) 的所有质数；

for (int i = 0 ; i < size && P[i]<=sq ; i++){
          nd = 1;
          while(n%P[i]==0){
               n/=P[i];
               nd++;
               }
          count*=nd;
          if (n==1)break;
          }
      if (n!=1)count*=2;//the confusing line :D :P .

     i will lift the understanding for the reader  .
     i now look forward to a method more optimized  .
1
以下是一个C程序，用于查找给定数字的因数数量。
该算法的复杂度为O(sqrt(n))。
该算法对于完全平方数以及非完全平方数都可以正常工作。
请注意，循环的上限被设置为数字的平方根，以使算法最有效。
请注意，将上限存储在单独的变量中也节省了时间，不应在for循环的条件部分调用sqrt函数，这也节省了计算时间。
#include<stdio.h>
#include<math.h>
int main()
{
    int i,n,limit,numberOfDivisors=1;
    printf("Enter the number : ");
    scanf("%d",&n);
    limit=(int)sqrt((double)n);
    for(i=2;i<=limit;i++)
        if(n%i==0)
        {
            if(i!=n/i)
                numberOfDivisors+=2;
            else
                numberOfDivisors++;
        }
    printf("%d\n",numberOfDivisors);
    return 0;
}

除了上面的for循环，您还可以使用以下更高效的循环，因为它不需要找到数字的平方根。

for(i=2;i*i<=n;i++)
{
    ...
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接