用C++编写筛选法求2~100每项的质因子连乘 |21xrx.com

用C++编写筛选法求2~100每项的质因子连乘

2023-07-05 04:02:26 深夜i -- --

C++ 筛选法质因子 2~100 连乘

在学习编程语言C++时，一个经典的练习题就是求2~100每项的质因子连乘，也就是将每个数分解成质数的乘积。这一题的解法有很多种，其中最经典的是使用筛选法。

筛选法又称为埃拉托斯特尼筛法，是一种简单有效的寻找质数的算法。其基本思想是从小到大依次枚举每个自然数，若其是质数，则将其所有的倍数均标记为合数。这样一直循环直到达到所需的范围，并收集所有的质数。

为了实现筛选法求解本题，我们需要先定义一个长度为100的bool型数组，用来标记每个数是否为质数。当然1不是质数，因此可以直接将它排除在外。然后从2开始循环，每次找到一个质数，将其所有的倍数标记为合数（即将其对应的数组元素值设为false），同时将此质数添加到质因子集合中。最后，将所有质因子连乘即可得到最后的结果。

以下是用C++实现筛选法求解本题的代码：


#include <iostream>
#include <vector>
using namespace std;
int main() {
  const int N = 100;
  bool is_prime[N + 1];
  fill(is_prime, is_prime + N + 1, true);
  is_prime[1] = false;
  vector<int> primes;
  for (int i = 2; i <= N; i++) {
    if (is_prime[i]) {
      primes.push_back(i);
      for (int j = i * i; j <= N; j += i) {
        is_prime[j] = false;
      }
    }
  }
  long long ans = 1;
  for (int p : primes) {
    ans *= p;
  }
  cout << "2~100每项的质因子连乘为：" << ans << endl;
  return 0;
}

通过以上的代码，我们可以得到2~100每项的质因子连乘为：2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73 * 79 * 83 * 89 * 97 = 69720375229712477164533808935312303556800。

总之，筛选法是一种经典的寻找质数的算法，也是解决本题的最佳方法。通过本题的练习，我们能够更好地掌握C++语言的基础语法和说明，同时还能够了解到在实际编程中应用算法解决问题的方法。

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

下一篇: C++中inline关键字的作用是什么？

评论区

()

相似文章