c - 在c中找到合数的最大质因数

Question

我正在接受一个合数作为输入。我想打印它的所有因子以及该数的最大质因数。我写了下面的代码。它在数字 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);
}

Answer 1

这有点剧透，所以如果您想自己解决这个问题，请先不要阅读:)。我会尽量按顺序提供提示，这样您就可以按顺序阅读每个提示，如果您需要更多提示，请转到下一个提示，等等。

提示 #1: 如果除数是n的约数，则n/除数也是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/除数的其他因数。我们可以使用 sieve接近并标记我们找到的因素。

提示 #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.