我想找到一个数的所有因子。
目前我有这样的代码：
{
int n;
int i=2;
scanf("%d",&n);
while(i<=n/2)
{
if(n%i==0)
printf("%d,",i);
i++;
}
getch();
}
有没有什么办法可以改善它？
寻找给定整数的所有精确除数的算法
24
- jairaj
7个回答
61
首先，你的代码应该有条件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。 - 如果想以升序显示所有因子，请将值存储在数组中，然后在循环结束时对所有数字进行排序并显示。
- Rndm
7
4
使用“找到所有质因数”的方法在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;
}
- ManAndPC
2
简单的线性搜索可以通过首先排除所有2的因子来改进。这可以通过简单的位移或使用一个很好的内在函数计算零数来完成。无论哪种情况，都非常快速。然后运行shg建议的算法（现在没有2的幂了，所以速度会快得多），并将结果与所有可能的2的幂组合起来（不要忘记这一步）。对于有许多零数的输入，它有很大的帮助，但即使它们没有也有帮助——您不再需要测试任何偶数除数，因此循环长度减半。
排除一些恒定的低因子（但大于2）也可以有所帮助。用常数取模几乎肯定由编译器优化（如果没有，您可以自己执行），但更重要的是，这意味着剩下要测试的除数更少了。不要忘记将该因子与您找到的除数组合起来。
您还可以完全分解数字（使用您喜欢的算法——可能是Pollard's Rho最好），然后打印所有因子的乘积（除了空乘积和完整乘积）。对于更大的输入，这有很大的几率比简单的线性搜索更快——Pollard's Rho算法相对于简单的线性搜索非常快地找到因子，通常情况下因子比真正的除数少，并且最后一步（枚举乘积）只涉及快速数学运算（无需除法）。这主要有助于具有非常小因子的数字，Rho可以最快地找到这些因子。
排除一些恒定的低因子（但大于2）也可以有所帮助。用常数取模几乎肯定由编译器优化（如果没有，您可以自己执行），但更重要的是，这意味着剩下要测试的除数更少了。不要忘记将该因子与您找到的除数组合起来。
您还可以完全分解数字（使用您喜欢的算法——可能是Pollard's Rho最好），然后打印所有因子的乘积（除了空乘积和完整乘积）。对于更大的输入，这有很大的几率比简单的线性搜索更快——Pollard's Rho算法相对于简单的线性搜索非常快地找到因子，通常情况下因子比真正的除数少，并且最后一步（枚举乘积）只涉及快速数学运算（无需除法）。这主要有助于具有非常小因子的数字，Rho可以最快地找到这些因子。
- harold
3
你能举个例子展示如何通过位移操作来移除所有2的因数吗？位运算更快，这肯定会提高性能。 - jairaj
@jairaj说你拿24，它的平方根接近5但不完全相等，所以你需要测试除数2、3和4（分别生成12、8和6）。如果你去掉所有的2的幂，你就剩下了3。只有3。3的平方根小于2，因此您不需要测试任何除数。所以你从3个缓慢的除法变成了零个除法+几次移位（首先是去除2的幂，然后稍后再添加回来）。一个明显的胜利。 - harold
@jairaj 关于合并：你将有3个2的幂次方：2、4和8。这些都是除数。现在将它们每个乘以3（“所有”其他除数，其中恰好只有一个），得到6、12和24。然后丢掉24，因为它不是一个适当的除数。 - harold
1
这是我的新版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;
}
- AustrianHunter
0
在其中一个答案中呈现的代码存在一个难以一眼看出的错误。如果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();
}
- Duckman
0
当给定的数字为奇数时，我们甚至可以跳过偶数。 接受代码的轻微改进 :)
这是查找给定数字因子的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 + ", ");
}
}
}
}
}
}
}
- manohar e
0
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;
- Himanshu Jain
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
printf("%d,", i);printf("%d,", n/i);改为printf("%d,", i); if(i != n/i){printf("%d,", n/i);}。对于一个完全平方数，它不会打印两次根数。 - MYMNeoi < sqrt(n)来避免多次检查n/i != i，这意味着n/i != i，然后像单独的边缘情况一样在while循环外检查i=sqrt(n)。 - chepneri <= sqrt(n)会将 i 提升为 double 类型。你可以使用i <= (int)sqrt(n)来避免这种情况。将if (i != (n / i))改为if (i*i != n)可以提高代码的运行速度。 - rcgldr