3

我接受一个复合数作为输入。我想打印它的所有因子以及该数字的最大素因子。我已经编写了以下代码。在数字 51 之前它工作得很好。但是如果输入任何大于 51 的数字，则会显示错误的输出。如何更正我的代码？

#include<stdio.h>
void main()
{
 int i, j, b=2, c;
 printf("\nEnter a composite number: ");
 scanf("%d", &c);
 printf("Factors: ");

 for(i=1; i<=c/2; i++)
 {
  if(c%i==0)
  {
   printf("%d ", i);
   for(j=1; j<=i; j++)
   {
    if(i%j > 0)
    {
     b = i;
    }
    if(b%3==0)
     b = 3;
    else if(b%2==0)
     b = 2;
    else if(b%5==0)
     b = 5;
   }
  }
 }
 printf("%d\nLargest prime factor: %d\n", c, b);
}
4

5 回答 5

8

这有点剧透，所以如果您想自己解决这个问题，请不要阅读此内容:)。我将尝试按顺序提供提示，因此您可以按顺序阅读每个提示，如果您需要更多提示，请移至下一个提示等。

提示 #1： 如果 divisor 是 n 的除数，则 n / divisor 也是 n 的除数。例如，100 / 2 = 50 余数为 0，所以 2 是 100 的除数。但这也意味着 50 是 100 的除数。

提示 #2 给定提示 #1，这意味着我们可以在检查素因数时从 i = 2 循环到 i*i <= n。例如，如果我们检查数字 100，那么我们只需要循环到 10（10*10 <= 100），因为通过使用提示 #1，我们将获得所有因子。那是：

100 / 2 = 50, so 2 and 50 are factors
100 / 5 = 20, so 5 and 20 are factors
100 / 10 = 10, so 10 is a factor

提示 #3 因为我们只关心 n 的质因数，只要找到 n 的第一个因数就足够了，称之为除数，然后我们可以递归地找到 n / 除数的其他因数。我们可以使用筛分法，并在发现因素时将其标记出来。

提示 #4 示例解决方案C：

bool factors[100000];

void getprimefactors(int n) {
  // 0 and 1 are not prime
  if (n == 0 || n == 1) return;

  // find smallest number >= 2 that is a divisor of n (it will be a prime number)
  int divisor = 0;
  for(int i = 2; i*i <= n; ++i) {
    if (n % i == 0) {
      divisor = i;
      break;
    }
  }
  if (divisor == 0) {
    // we didn't find a divisor, so n is prime
    factors[n] = true;
    return;
  }

  // we found a divisor
  factors[divisor] = true;
  getprimefactors(n / divisor);
}

int main() {
  memset(factors,false,sizeof factors);
  int f = 1234;
  getprimefactors(f);
  int largest;
  printf("prime factors for %d:\n",f);
  for(int i = 2; i <= f/2; ++i) {
    if (factors[i]) {
      printf("%d\n",i);
      largest = i;
    }
  }
  printf("largest prime factor is %d\n",largest);
  return 0;
}

输出：

---------- Capture Output ----------
> "c:\windows\system32\cmd.exe" /c c:\temp\temp.exe
prime factors for 1234:
2
617
largest prime factor is 617
> Terminated with exit code 0.
于 2010-08-12T18:58:47.137 回答
3

我想你这样做是为了学习，所以我希望你不介意提示。

我将首先在一个失败的数字上逐步执行您的算法。这是否向您显示错误在哪里？

于 2010-08-12T18:31:56.730 回答
2

您需要重新编码，以便您的代码找到给定数字的所有素数，而不仅仅是计算素数 2、3 和 5。换句话说，您的代码只能使用您正在计算的数字是质数 or 是 2、3 或 5 的倍数。但 7、11、13、17、19 也是质数 - 因此您的代码应该通过查找特定数字的所有因子并返回最大因子来工作不能进一步整除。

于 2010-08-12T18:31:17.533 回答
0

简化 dcp 的答案（以迭代方式）：

#include <stdio.h>
void factorize_and_print(unsigned long number) {
  unsigned long factor;
  for(factor = 2; number > 1; factor++) {
    while(number % factor == 0) {
      number = number / factor;
      printf("%lu\n",factor);
    }
  }
}

/* example main */
int main(int argc,char** argv) {
  if(argc >= 2) {
    long number = atol(argv[1]);
    factorize_and_print(number);
  } else {
    printf("Usage: %s <number>%<number> is unsigned long", argv[0]);
  }
}

注意：这里有一个数字解析错误，无法正确获取 argv 中的数字。

于 2012-10-21T03:20:18.467 回答
0

确实，除了最小的数字（例如，100,000 以下）之外，这对于所有数字都非常慢。试着找出这个数字的主要因数：

#include <cmath>

void addfactor(int n) {
    printf ("%d\n", n);
}

int main()
{
    int d;
    int s;
    int c = 1234567;
    while (!(c&1)) {
        addfactor(2);
        c >>= 1;
    }
    while (c%3 == 0) {
        addfactor(3);
        c /= 3;
    }
    s = (int)sqrt(c + 0.5);
    for (d = 5; d <= s;) {
        while (c % d == 0) {
            addfactor(d);
            c /= d;
            s = (int)sqrt(c + 0.5);
        }
        d += 2;
        while (c % d == 0) {
            addfactor(d);
            c /= d;
            s = (int)sqrt(c + 0.5);
        }
        d += 4;
    }
    if (c > 1)
        addfactor(c);
    return 0;
}

其中 addfactor 是将因子添加到主要因子列表中的某种宏。一旦你有了这些，你就可以构建一个数字的所有因素的列表。

这比此处发布的其他代码片段要快得多。对于像 10597959011 这样的随机输入，我的代码需要 2000 位运算加上 1000 多个位运算来重新构成除数，而其他代码则需要数十亿次运算。在这种情况下，这是“即时”和一分钟之间的区别。

于 2010-08-12T18:59:13.717 回答