C++判断素数的方法 |21xrx.com

C++判断素数的方法

2023-07-04 19:19:20 深夜i -- --

C++ 素数判断方法

素数指的是只能够被1和自己本身整除的数。在计算机编程中，判断一个数是否为素数是一种常见的问题。在C++中也有多种方法来判断一个数是否是素数。

首先，最基本的方法就是使用循环来判断。从2开始，一直循环到这个数的平方根（因为一个数分解质因数时，其中一个数一定在它的平方根以下），如果有一个数能够整除这个数，那么这个数就不是素数。否则，这个数就是素数。具体实现如下：


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

除了使用循环，还可以使用更高效的算法来判断素数。其中，最常见的算法就是埃氏筛法（Sieve of Eratosthenes）。这个算法的基本思想是先将一个范围内的数全部标为素数，然后从2开始，如果这个数标为素数，那么将它后面所有能被它整除的数标为非素数。最后剩下的被标为素数的数就是素数。具体实现如下：


vector<int> getPrimes(int n) {
  vector<int> res;
  vector<bool> isPrime(n + 1, true);
  for (int i = 2; i <= n; i++) {
    if (isPrime[i]) {
      res.push_back(i);
      for (int j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  return res;
}

以上是C++中判断素数的两种方法，可以根据具体的场景选择不同的方法来判断素数。在实际编程中，可以根据需要对这些方法进行改进和优化，以达到更高的效率。

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

下一篇: 如何使用c++创建多个黑色终端窗口

评论区

()

相似文章