C++程序：素数分解 |21xrx.com

C++程序：素数分解

2023-07-04 23:52:30 深夜i -- --

C++ program prime factorization

素数分解是指将一个正整数分解为若干个素数的乘积。在计算机领域中，素数分解常常被利用于密码学和质因数分解问题上。C++是一种常见的编程语言，在C++程序中实现素数分解也非常容易。

首先，我们需要定义一个函数来判断一个数是不是素数。一个数可以被分解成若干个质数的乘积，那么它本身就是一个质数，那么这个数只能被1和它本身整除，不能被其他数整除。而判断一个数能否被另一个数整除可以利用取模运算。


bool isPrime(int n) {
  if(n < 2) return false;
  for(int i = 2; i <= sqrt(n); i++) {
    if(n % i == 0) return false;
  }
  return true;
}

接着，我们写一个函数来对一个数进行素数分解。在分解的过程中，我们需要从2开始向上依次判断每一个数是否是该数的因子，如果是，就将该数除以这个因子并将这个因子放入结果集合中。


vector<int> decompose(int n) {
  vector<int> res;
  for(int i = 2; i <= n; i++) {
    while(n % i == 0 && isPrime(i)) {
      res.push_back(i);
      n /= i;
    }
  }
  return res;
}

对于一个较大的数而言，素数分解可能需要花费较长的时间，因此我们可以对上述函数进行优化，提高效率。事实上，我们只需要将2到根号n的所有质数作为因子进行判断就可以了。因为如果一个数n有一个大于根号n的因子，那么这个因子一定有一个小于根号n的因子，而这个小于根号n的因子已经被判断过了。


vector<int> decompose(int n) {
  vector<int> res;
  for(int i = 2; i <= sqrt(n); i++) {
    while(n % i == 0 && isPrime(i)) {
      res.push_back(i);
      n /= i;
    }
  }
  if(n > 1) res.push_back(n);
  return res;
}

最后，我们可以将上述两个函数组合起来，在主函数中输入待分解的数，然后对该数进行素数分解，并输出分解结果。


int main() {
  int n;
  cin >> n;
  vector<int> res = decompose(n);
  for(auto e : res)
    cout << e << " ";
  
  cout << endl;
  return 0;
}

通过上述C++程序的运行，我们就可以将一个正整数分解为若干个素数的乘积。这可以让我们更好地理解正整数的构成，并且对于数字的一些应用也有很大的帮助。同时，C++也是一种非常实用的编程语言，在计算机领域中非常重要。

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

下一篇: "Dev C++中如何添加头文件？"

评论区

()

相似文章