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

C++中的素数判断

2023-07-10 09:51:43 深夜i -- --

C++ 素数判断

素数是指在除了1和自身之外，不能被其他正整数整除的数。在编程中，常常需要使用素数判断。C++是一门强大的编程语言，它提供了多种方法来进行素数判断。

最常规的方法是通过循环判断，如果一个数只能被1和自身整除，那么它就是素数。以下是一个基于循环的素数判断代码：


bool isPrime(int n){
  if(n <= 1) return false; //特判1和0
  for(int i=2; i*i <= n; i++){
    if(n%i == 0) return false; //如果有一个数整除它，那么它不是素数
  }
  return true;
}

通过循环遍历2到n-1，对于每一个数i，如果n能整除i，那么就不是素数了。但是这种方法存在一个问题，时间复杂度比较高，对于大于10000的数，它需要遍历10000次才能进行判断。为了解决这个问题，我们可以使用更高效的算法。

第二种方法是埃氏筛法。它的基本思想是，将所有数标记为素数，从2开始，将所有能被2整除的数标记为非素数，然后从3开始，将所有能被3整除的数标记为非素数，以此类推，直到n。标记完毕后，剩下的没有被标记的数就是素数。

以下是一个基于埃氏筛法的素数判断代码：


bool isPrime(int n){
  if(n <= 1) return false; //特判1和0
  bool prime[n+1]; //创建一个bool型数组，用于储存每个数是否为素数
  memset(prime,true,sizeof(prime)); //初始化为true（素数）
  for(int i=2; i*i <= n; i++){
    if(prime[i]){ //如果i是素数
      for(int j=i*i; j <= n; j+=i){ //将能被i整除的数标记为非素数
        prime[j] = false;
      }
    }
  }
  return prime[n]; //返回n是否为素数
}

这种方法的时间复杂度为O(loglogn)，要比第一种方法高效得多，因此在实际使用中，建议优先选择埃氏筛法。

综上所述，素数判断在编程中是非常常见的，C++提供了多种方法来进行素数判断，不同的算法具有不同的时间复杂度和效率，可以根据实际需要选择合适的算法。

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

下一篇: C++能够调用安卓的所有API吗？

评论区

()

相似文章