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

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所建议的那样.
• 如果您希望所有因子按升序存储数组中的值,则在循环结束时对所有数字进行排序并显示.