C++求最大质因子 |21xrx.com

C++求最大质因子

2023-07-06 15:21:46 深夜i -- --

C++ 最大质因子求解

在计算机编程中，求最大质因子是一个比较常见的任务。对于C++程序员而言，这个任务并不难实现。下面将介绍两种方法，让大家轻松掌握求最大质因子的技巧。

方法一：暴力枚举

暴力枚举的方法比较直观。我们可以从2开始，依次判断每个数是否是给定数的因子，如果是则将其存储，以此类推直到枚举到该数的一半，最后输出存储下来的最大质因子。

以下是该方法的实现代码：


#include<iostream>
using namespace std;
int main() {
  long long num=600851475143;  // 待求最大质因子的数
  long long max_factor=0;    // 最大质因子
  for(long long i=2; i<=num/2; i++) { // 从2到数的一半进行枚举
    if(num%i==0) { // 如果i是num的因数
      bool is_prime=true; // 设置标记，表示i是否为质数
      for(long long j=2; j<=i/2; j++) { // 从2到i的一半进行枚举
        if(i%j==0) // 如果i能被j整除
          is_prime=false; // 则i不是质数
          break; // 退出循环
        
      }
      if(is_prime) // 如果i是质数
        max_factor=i; // 则将i作为最大质因子
      
    }
  }
  cout<<"最大质因子为："<<max_factor<<endl; // 输出最大质因子
  return 0;
}

该方法的主要思路是暴力穷举，需要枚举2到数的一半的所有数。时间复杂度为O(n^2)，所以该方法在面对比较大的数时会比较耗时。

方法二：分解质因数

分解质因数的方法相比暴力枚举更为快捷。我们可以先对待求最大质因子的数进行分解质因数，然后将得到的质因数从小到大进行排列，输出最大的一个即为所求最大质因子。分解质因数的方法再用较多时单独做介绍。

以下是该方法的实现代码：


#include<iostream>
using namespace std;
int main() {
  long long num=600851475143; // 待求最大质因子的数
  long long max_factor=0;   // 最大质因子
  for(long long i=2; i<=num; i++) { // 从2开始，依次判断每个数是否为num的因数
    if(num%i==0) { // 如果i是num的因数
      if(i>=max_factor) // 如果i比最大质因子还大
        max_factor=i; // 则将i作为最大质因子
      
      while(num%i==0) // 将num中所有的i因子全部除去
        num/=i;
      
    }
  }
  cout<<"最大质因子为："<<max_factor<<endl; // 输出最大质因子
  return 0;
}

该方法的时间复杂度为O(sqrt(n))，比暴力枚举的方法要快得多。这也是为什么很多情况下分解质因数的方法比暴力枚举更受欢迎的主要原因。

总结一下，C++程序员可以通过暴力枚举和分解质因数两种方法来求最大质因子。在实际应用时，程序员需根据所处理数据的大小选取不同的方法，以提高程序效率。

上一篇: idea打包java可执行jar包

下一篇: C++ 封装算法实现加密功能

评论区

()

相似文章