C++代码：判断素数 |21xrx.com

C++代码：判断素数

2023-06-22 11:34:01 深夜i -- --

C++ 素数判断

素数是指只能被1和自身整除的正整数，比如2、3、5、7、11等。判断一个数是否为素数是数学中的一个经典问题。下面介绍如何用C++代码来判断一个数是否为素数。

方法1：试除法

试除法是最简单的判断素数的方法，即对于一个数n，从2到n-1试图将n除尽，如果都不能除尽，则n是素数。

下面是用C++代码实现试除法的过程：


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

方法2：优化试除法

上面的方法1虽然简单，但是对于大数来说，效率非常低。因此我们可以对方法1进行优化。具体方法是：对于一个数n，只需要判断2到sqrt(n)之间的数是否能够整除n，如果都不能整除，则n是素数。

下面是用C++代码实现优化试除法的过程：


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

方法3：埃氏筛法

埃氏筛法是一种较高效的求素数的方法。具体方法是：从2开始，将每个素数的倍数都标记成合数，直到没有需要标记的数为止。

下面是用C++代码实现埃氏筛法的过程：


const int MAXN = 100000; // 筛选范围
int prime[MAXN/3+1]; // 存放素数
bool is_prime[MAXN+1]; // 记录是否为素数
int num = 0; // 素数个数
void sieve()
{
  for(int i = 2; i <= MAXN; i++)
  {
    if(!is_prime[i])
    {
      prime[num++] = i; // 存下素数
      for(int j = i*2; j <= MAXN; j += i)
      {
        is_prime[j] = true; // 标记为合数
      }
    }
  }
}

通过上述三种判断素数的方法，你可以轻松地用C++代码来判断任意一个数是否为素数。无论你是初学者还是已经掌握了C++编程语言，这些方法都是非常实用的，希望能够对你有所帮助。

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

下一篇: C++中public和private的作用探究

评论区

()

相似文章