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

C++判断素数的方法

2023-07-04 22:58:05 深夜i -- --

C++ 判断素数方法

素数，指的是只能被1和本身整除的自然数。在数学理论中，素数是非常重要的一个概念，在许多领域都有广泛的应用。在程序设计中，判断素数也是常见的问题。C++作为一门流行的编程语言，也提供了多种方法来判断一个数是不是素数。

以下是几种C++判断素数的方法：

1.暴力算法：常规的判断素数的方法是用循环来判断这个数是否可以被其他比它小的数整除。如果不能整除，那么这个数就是素数。这个方法的时间复杂度是O(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;
}

2.优化算法1：可以看出，判断一个数是否是素数，只需判断它能否被范围在2到根号n之间的自然数整除，就可以得出结论。这个方法的时间复杂度是O(根号n)。

示例代码：


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

3.优化算法2：但是，还是有一些问题需要解决。比如，如果要判断多个数，每个数都需要使用这个循环判断，会造成很大的时间开销。我们可以把判断的结果保存下来，下次遇到同一个数时直接用已经计算好的结果。这个方法称为素数筛选。时间复杂度是O(n*loglogn)。

示例代码：


int is_primer[1000005]; //全局，自动初始化为0
void checkisPrimer(int n){
  for(int i=2;i<=sqrt(n);i++){  // 注意外层循环的上限
    if(!is_primer[i]){     // 使用数组保存计算好的结果
      for(int j=i*i;j<=n;j+=i){
        is_primer[j]=1;
      }
    }
  }
}
bool isPrime(int n){
  if(n<=1) return false;
  return !is_primer[n];      // 使用数组保存计算好的结果
}

这几种方法都可以用来判断一个数是否是素数，基础的暴力算法实现简单，但耗时长；而优化算法可以在保证精度的情况下，大大提升运算效率。在程序设计中判断素数也是很有用的技能，可以应用到许多方面，比如密码学和计算机科学等领域。

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

下一篇: C++变量作用域：全局变量和局部变量的区别说明

评论区

()

相似文章