C++实现完全数的求解——辗转相除法 |21xrx.com

C++实现完全数的求解——辗转相除法

2023-06-24 19:05:19 深夜i 31 0

C++ 完全数求解辗转相除法

在数学中，完全数指所有真因子之和等于它本身的数。例如，6 = 1 + 2 + 3。那么如何用C++来实现完全数的求解呢？我们可以使用辗转相除法来完成这个任务。

辗转相除法是一种常用的求最大公约数和最小公倍数的方法，而完全数的求解需要用到最大公约数。我们可以使用这个算法来求一个数的所有真因子之和。

假设要求解的数为n，我们可以从2到n/2遍历每一个的数i，检查n是否可以被i整除。如果可以，将i加入真因子列表，并将n除以i，继续检查余数是否为零。如果余数不为零，继续增加i的值。如果余数为零，我们就得到了该数的所有真因子。最后，我们可以将所有真因子相加，得到完全数的结果。

下面是C++的实现代码：

#include <iostream>
using namespace std;
int main() {
  int n = 28; // 求解的数
  int sum = 1; // 1是所有数的真因子，从1开始累加
  for (int i = 2; i <= n / 2; i++) {
    if (n % i == 0) {
      sum += i;
      n /= i;
      i--;
    }
  }
  if (n > 1) { // 如果最后还有一个大于n/2的质因数
    sum += n;
  }
  if (sum == n)
    cout << n << "是完全数" << endl;
   else
    cout << n << "不是完全数" << endl;
  
  return 0;
}

上面的代码输出28是完全数的结果。我们可以将代码中的n改成其他数，以求解其他完全数。

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

下一篇: C++ 封装 C 语言的特性

评论区

相似文章