查找给定整数的所有精确除数的算法
我想找到一个数字的所有确切除数。 目前我有这个：
{ int n; int i=2; scanf("%d",&n); while(i<=n/2) { if(n%i==0) printf("%d,",i); i++; } getch(); } 有没有办法改善它？
首先，您的代码应具有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(); }
注意 ：
- 对于一个完美的正方形，使得平方根不会打印两次，在@chepner建议的
i*i == n的循环结束时进行附加检查。 - 如果您希望所有因子按升序存储数组中的值，则在循环结束时对所有数字进行排序并显示。
通过在C（更快）和最多18位数中使用“查找所有素数因子”来查找所有除数。
#include #include #include #include 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的因子来改善。这可以通过简单的位移，或用一个很好的内在函数计数训练零来完成。 无论哪种情况，这都非常快。 然后运行shg建议的算法（由于两个幂不存在，它将运行得更快），并将结果与两个所有可能的幂相结合（不要忘记这一步）。 它对很多训练为零的输入有很大帮助，但如果它们没有，它甚至会有所帮助 – 你不必再测试任何偶数除数，所以循环变长了一半。
抛出一些恒定的低因子（但大于2）也会有所帮助。 带有常量的模数几乎肯定会被编译器优化（或者如果没有，你可以自己完成），但更重要的是，这意味着需要更少的除数来测试。 不要忘记将这个因素与你找到的除数结合起来。
您也可以完全分解数字（使用您最喜欢的算法 – 可能是Pollard的Rho最好），然后打印因子的所有产品（空产品和完整产品除外）。 这很有可能最终更快地获得更大的输入 – 与简单的线性搜索相比，Pollard的Rho算法很快找到因子，通常比适当的除数更少因素，最后一步（枚举产品）只涉及快速数学（没有分歧）。 这主要有助于数量非常小的数字，Rho发现最快。
其中一个答案中的代码有一个乍一看很难看到的错误。 如果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(); }
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;
当给定的数字是奇数时，我们甚至可以跳过偶数。 在接受的代码中轻微即兴:)
这里是用于查找给定数字的因子的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 + ", "); } } } } } } }
这是我的新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; }