找到一个给定的整数的所有确切的除数算法(Algorithm to find all the exac

我想找到一个号码的所有确切的除数。 目前，我有这样的：

{
   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 ，否则它可以错过的因素之一，例如6将不被打印如果n = 12。

运行回路的数量的平方根（即， 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的建议。
• 如果你想按升序排列的所有因素，然后存储值数组在循环排序所有的数字和显示的结束。

Answer 2:

通过查找所有除数“发现的所有质因数”，在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;
}

Answer 3:

简单的线性搜索可以先投出的2所有这些因素都可以通过简单的比特移位来实现，或者算上训练Zero的一个不错的固有功能得到改善。 这是在任何情况下都很快。 然后运行通过SHG提出的算法（它现在运行得更快的是两个权力不存在），并将结果与​​两所有可能的力量结合起来（不要忘记这一步）。 它帮助了很多有大量的培训零的输入，但如果他们不它甚至可以帮助 - 你就不必再测试任何甚至除数，所以循环将成为一半的时间。

投掷了一些恒定的低的因素（但大于2）也有帮助。 模以恒定几乎可以肯定是由编译器优化（或者如果没有，你可以自己做），但更重要的是，这意味着有更少的除数留下来测试。 不要忘了这个因素与你找到除数相结合。

您也可以完全因式分解的数量（使用自己喜欢的算法 - 可能波拉德的Rho将是最好的），然后打印所有产品（除空的产品和完整的产品）的因素。 这有结束了是更大的输入速度更快的一个好机会 - 波拉德的Rho算法找到因素相比，一个简单的线性搜索速度非常快，也有因素，而不是正确的除数一般较少，而最后一步（列举的产品）只涉及快速数学（无师）。 这主要是有助于对数字非常小的因素，其中卢找到最快的。

Answer 4:

在其中一个答案呈现代码有缺陷，这是很难看到的第一眼。 如果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();
}

Answer 5:

  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;

Answer 6:

当给定数是奇数，我们甚至可以跳过偶数。 在接受代码略有即兴:)

这对于找到给定数量的因素的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 + ", ");
                        }
                    }
                }
            }
        }
    }
}

Answer 7:

这是我新的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;
    }

文章来源: Algorithm to find all the exact divisors of a given integer