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

Question

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

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

有什么办法可以改善它？

Answer 1

首先，您的代码应具有条件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建议在循环末尾进行其他检查。
• 如果希望所有因子按升序存储在数组中，则在循环末尾对所有数字进行排序并显示。