C++求质因子的方法 |21xrx.com

C++求质因子的方法

2023-07-08 01:02:40 深夜i -- --

C++ 求质因子方法

C++是一种广泛使用的编程语言，在计算机编程中具有广泛的应用。如果您正在使用C++编写程序以寻找给定数的质因子，可以按照下面的方法进行。

方法一：

首先，计算给定数字n的平方根。然后从2开始，对n每个数进行测试，以确定它是否为n的因子。如果它是，将它加入到结果向量中，并将n除以该数。接着，继续对n进行测试，直到n等于1。

例如，假设要寻找1296的质因子。首先，计算其平方根 36。从2开始测试，我们测试了2, 3, 4, 6, 8和9。测试时，我们发现2, 3和6是它的因数。因此，我们将它们添加到结果向量中，1296/2=648，继续测试。接着，我们找到4和8是它的因数，所以将它们添加到向量中，继续测试。最后，它的因数9添加到向量中。此时，n的值等于1，寻找因数过程结束。结果向量中的值是2。

下面是C++代码：


#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int main(){
  int num;
  vector<int> result;
  cout << "Enter a number: ";
  cin >> num;
  int root = sqrt(num);
  for (int i = 2; i <= root; i++) {
    while (num % i == 0) {
      result.push_back(i);
      num /= i;
    }
  }
  if (num != 1) {
    result.push_back(num);
  }
  for (int i = 0; i < result.size(); i++) {
    cout << result[i] << " ";
  }
}

方法二：

该方法使用欧拉筛法，可以更快速地寻找质因子。

首先，使用欧拉筛法来预处理所有质数。然后，将输入的数字分解为最小的质因子。继续除以最小质因数，直到不能再继续分解。

例如：假设要寻找1000的质因子。首先，标记2, 3和5是质数，保留到一个数组中。然后，将其分解为其最小质因数2和500。继续分解为最小质因数2和250，最终的质因数表为2, 2, 2, 5和5。

以下是C++代码：


#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
vector<int> prime;
void precompute() {
  bool is_prime[1000000];
  memset(is_prime, true, sizeof(is_prime));
  for (int i = 2; i <= 1000000; i++)
  {
    if (is_prime[i])
    {
      prime.push_back(i);
      for (int j = i * i; j <= 1000000; j += i)
      {
        is_prime[j] = false;
      }
    }
  }
}
void factorization(int n) {
  int idx = 0;
  while (prime[idx] * prime[idx] <= n) {
    if (n % prime[idx] == 0) {
      cout << prime[idx] << " ";
      n /= prime[idx];
    }
    else {
      idx++;
    }
  }
  if (n > 1)
    cout << n << " ";
  
}
int main() {
  precompute();
  int n;
  cout << "Enter a number: ";
  cin >> n;
  factorization(n);
 
}

以上就是在C++中寻找给定数的质因子的两种方法，您可以根据自己的需要选择。无论您选择哪种方法，都可以帮助您快速找到给定数字的质因子。

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

下一篇: 使用C++开发安卓应用

评论区

()

相似文章