一尘不染

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

algorithm

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

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

有什么办法可以改善它?


阅读 434

收藏
2020-07-28

共1个答案

一尘不染

首先,您的代码应具有条件i <= n/2,否则它可能会遗漏其中一个因素,例如,如果n = 12,则不会打印6。

将循环运行到数字的平方根(即i <= sqrt(n)),并同时打印in/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建议在循环末尾进行其他检查。
  • 如果希望所有因子按升序存储在数组中,则在循环末尾对所有数字进行排序并显示。
2020-07-28