在c中查找复合数的最大素数因子

发布时间：2020-12-16 10:27:58 所属栏目：百科来源：网络整理

导读：我接受一个复合数作为输入.我想打印它的所有因素,也是这个数字的最大素数因子.我写了以下代码.它完全正常,直到数字51.但是如果输入任何大于51的数字,则显示错误的输出.我怎样才能纠正我的代码？ #includestdio.hvoid main(){ int i,j,b=2,c; printf("nEnter

我接受一个复合数作为输入.我想打印它的所有因素,也是这个数字的最大素数因子.我写了以下代码.它完全正常,直到数字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("%dnLargest prime factor: %dn",c,b);
}

解决方法

这是一个扰流板,所以如果你想自己解决这个问题,请不要读这个:).我将尝试按顺序提供提示,因此您可以按顺序阅读每个提示,如果您需要更多提示,请转到下一个提示,等等.

提示#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("%dn",i);
      largest = i;
    }
  }
  printf("largest prime factor is %dn",largest);
  return 0;
}

输出：

---------- Capture Output ----------
> "c:windowssystem32cmd.exe" /c c:temptemp.exe
prime factors for 1234:
2
617
largest prime factor is 617
> Terminated with exit code 0.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!