C++如何判断一个整数是否为素数？ |21xrx.com

C++如何判断一个整数是否为素数？

2023-07-05 11:54:18 深夜i -- --

C++ 判断整数素数

素数是指只能被1和自身整除的正整数。在计算机编程中，判断一个整数是否为素数是常见的问题。C++中可以使用以下几种方法来判断一个整数是否为素数。

方法一：暴力枚举法

暴力枚举法是指依次枚举从2到n-1的每个数，判断它们是否能够整除n。如果能够整除，那么n就不是素数。如果枚举完了所有的数都不能整除n，那么n就是素数。

代码如下：


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

方法二：优化枚举法

暴力枚举法虽然简单易懂，但是效率较低，特别是当n较大时，时间复杂度为O(n)。为了提高效率，可以进行一些优化。

首先，可以通过排除偶数来减少循环次数。因为偶数除2外一定还有其他因数，所以可以直接排除除2以外的偶数。

其次，对于一个数n，如果它有因子x，则n/x也是它的因子，且它的因子必定成对出现，其中一个因子小于等于√n，另外一个大于等于√n。所以只需要枚举到√n即可。

代码如下：


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

方法三：筛法

筛法是一种常用的素数判别算法，其基本思想是从2开始，将每个素数的倍数都标记成合数，这样在后面的操作中就可以不考虑这些合数，从而提高效率。

具体实现可以使用埃氏筛法或欧拉筛法，这里以埃氏筛法为例。

代码如下：


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

以上就是C++中判断一个整数是否为素数的三种方法，分别是暴力枚举法、优化枚举法和筛法。在实际使用中，可以根据具体情况选择合适的方法，提高程序的效率。

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

下一篇: C++短路表达式简介

评论区

()

相似文章