查找给定整数的所有精确除数的算法

问题描述 投票：0回答：8

我想找到一个数字的所有精确除数。 目前我有这个：

{
   int n;
   int i=2;
   scanf("%d",&n);
   while(i<=n/2)
    {
        if(n%i==0)
                  printf("%d,",i);
        i++;
     }
   getch();
}

有什么办法可以改善吗？

c algorithm numbers performance factors
8个回答
62
投票

首先，你的代码应该满足

i <= n/2
的条件，否则可能会错过其中一个因素，例如如果n=12，则不会打印6。

运行循环到数字的平方根（即

i <= sqrt(n)
）并打印
i
和
n/i
（两者都是n的倍数）。

{
   int n;
   int i=2;
   scanf("%d",&n);
   while(i <= sqrt(n))
    {
        if(n%i==0) {
            printf("%d,",i);
            if (i != (n / i)) {
                printf("%d,",n/i);
            }
        } 

        i++;
    }
   getch();
}

注：

  • 对于完美平方，为了避免平方根被打印两次，额外的检查是在 
    i*i == n
    的循环末尾进行的，如 @chepner 所建议的。
  • 如果您希望所有因素按升序将值存储在数组中，则在循环结束时对所有数字进行排序并显示。
4
投票

使用C中的“查找所有素因数”来查找所有除数（更快） 最多 18 位数字。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

unsigned int FindDivisors(unsigned long long divisors[], unsigned long long N) {
    unsigned int lastdiv = 0;
    divisors[lastdiv++] = 1;
    unsigned long long powerfactor = 1;
    unsigned long long number = N;
    while ((number & 1) == 0) {
        powerfactor <<= 1;
        divisors[lastdiv++] = powerfactor;
        number >>= 1;
    }

    unsigned long long factor = 3; unsigned long long upto = lastdiv;
    powerfactor = 1;
    while (factor * factor <= number) {
        if (number % factor == 0) {
            powerfactor *= factor;
            for (unsigned int i = 0; i < upto; i++)
                divisors[lastdiv++] = divisors[i] * powerfactor;
            number /= factor;
        }
        else {
            factor += 2; upto = lastdiv;
            powerfactor = 1;
        }
    }

    if (number > 1) {
        if (number != factor) {
            upto = lastdiv;
            powerfactor = 1;
        }
        powerfactor *= number;
        for (unsigned int i = 0; i < upto; i++)
            divisors[lastdiv++] = divisors[i] * powerfactor;
    }
    return lastdiv;
}

int cmp(const void *a, const void *b) {
    if( *(long long*)a-*(long long*)b < 0 ) return -1;
    if( *(long long*)a-*(long long*)b > 0 ) return 1;
    return 0;
}

int main(int argc, char *argv[]) {
    unsigned long long N = 2;
    unsigned int Ndigit = 1;
    if (argc > 1) {
        N = strtoull(argv[1], NULL, 10);
        Ndigit = strlen(argv[1]);
    }
    unsigned int maxdiv[] = {1, 4, 12, 32, 64, 128, 240, 448, 768, 1344,
                             2304, 4032, 6720, 10752, 17280, 26880, 41472, 64512, 103680};

    unsigned long long divisors[maxdiv[Ndigit]];
    unsigned int size = FindDivisors(divisors, N);
    printf("Number of divisors = %u\n", size);

    qsort(divisors, size, sizeof(unsigned long long), cmp);
    for (unsigned int i = 0; i < size; i++)
        printf("%llu ", divisors[i]);
    printf("\n");

    return 0;
}
2
投票

可以通过首先丢弃 2 的所有因数来改进简单的线性搜索。这可以通过简单的位移位或使用良好的内函数对训练零进行计数来完成。无论哪种情况都非常快。然后运行 shg 建议的算法（由于不存在 2 的幂，运行速度会快得多），并将结果与所有可能的 2 的幂结合起来（不要忘记这一步）。它对于具有大量训练零的输入有很大帮助，但如果它们没有，它甚至会有所帮助 - 您不必再测试任何偶除数，因此循环的长度会缩短一半。

扔掉一些恒定的低因子（但大于 2）也有帮助。使用常量取模几乎肯定是由编译器优化的（或者如果没有，您可以自己优化），但更重要的是，这意味着需要测试的除数更少。不要忘记将该因子与您找到的除数结合起来。

您还可以完全分解数字（使用您最喜欢的算法 - 可能 Pollard 的 Rho 是最好的），然后打印因子的所有乘积（空乘积和满乘积除外）。对于更大的输入，这很有可能会更快 - 与简单的线性搜索相比，Pollard 的 Rho 算法可以非常快地找到因子，因子通常少于真除数，最后一步（枚举乘积）仅涉及快速数学（没有部门）。这对于因数非常小的数字很有帮助，Rho 发现这是最快的。

1
投票

这是我的新 C# 版本。感谢 Rndm，它比我第一次尝试快了几乎 50 倍。

public static long GetDivisors(long number)
    {
        long divisors = 0;

        long boundary = (long)Math.Sqrt(number);

        for (int i = 1; i <= boundary; i++)
        {
            if (number % i == 0)
            {
                divisors++;
                if(i != (number / i))
                {
                    if (i * i != number)
                    {
                        divisors++;
                    }
                }
            }
        }

        return divisors;
    }
0
投票

其中一个答案中提供的代码有一个乍一看很难发现的错误。如果 sqrt(n) 是有效除数；但 n 不是完全平方数，则省略两个结果。

例如尝试

n = 15
，看看会发生什么； 
sqrt(15) = 3
，所以while循环的最后一个值为2。执行的下一条语句
if (i * i == n)
将被执行为
if(3 * 3 == 15)
。所以 3 没有被列为除数，5 也被遗漏了。

以下将正确处理正整数的一般情况。

 {
   int n;
   int i=2;
   scanf("%d",&n);
   while(i <= sqrt(n))
    {
        if(n%i==0) {
            printf("%d,",i);
            if (i != (n / i)) {
                printf("%d,",n/i);
            }
        } 

        i++;
    }
   getch();
}
0
投票
  int count = 2;
     //long childsum = 0;
           long _originalvalue = sum;
     dividend = "1";
     for (int i = 2; i < sum; i++)
     {
         if (_originalvalue % i == 0)
         {
             sum = _originalvalue / i;
             //sum = childsum;
             dividend = dividend + "," + i+","+sum;
             if (sum == i)
             {
                 count++;
             }
             else
             {
                 count = count + 2;
             }
         }
     }
     return count;
0
投票

当给定的数字是奇数时，我们甚至可以跳过偶数。 对已接受的代码进行了轻微的即兴创作:)

这里是查找给定数字的因数的 Java 代码。

import java.util.Scanner;
public class Factors {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t=scanner.nextInt();
        while(t-- > 0) {
            int n = scanner.nextInt();
            if(n % 2 == 0) {
                for(int i = 1; i <= Math.sqrt(n); i++) {
                    if(n % i == 0) {
                        System.out.println(i + ", ");
                        if(i != n/i) {
                            System.out.println(n/i + ", ");
                        }
                    }
                }
            }
            else {
                for(int i = 1; i <= Math.sqrt(n); i=i+2) {
                    if(n % i == 0) {
                        System.out.println(i + ", ");
                        if(i != n/i) {
                            System.out.println(n/i + ", ");
                        }
                    }
                }
            }
        }
    }
}
0
投票

你的方法是一种幼稚的方法，我们从 2 迭代到 n/2，你可能会认为你能做的最好的保存就是迭代直到 n/2，但更好的方法是当你意识到你不这样做时甚至不需要多次迭代。 关键思想是，如果 i 是除数，则 n/i 也是除数。所以我们可以迭代所有 i，这意味着我们可以迭代 sqrt(n)（included）之前的数字。

void finding_divisors(std::vector<int>& div, int num) {
for (int i = 2; i <= std::sqrt(num); i++) {
    if (num % i == 0) {
        if (i != num / i) { 
            div.push_back(i);
            div.push_back(num / i);
        } else { 
            div.push_back(i);
        }
    }
}

}

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.