21xrx.com
2024-12-27 04:43:01 Friday
登录
文章检索 我的文章 写文章
C++中如何判断一个数是否为素数
2023-07-03 22:17:59 深夜i     --     --
C++ 判断 素数 算法

素数是指大于1的整数,除了1和它本身以外,无法被其他整数整除的数,如2、3、5、7、11等。在C++编程中,判断一个数是否为素数是一个基本的算法问题,下面介绍几种实现方式。

方法一:暴力枚举法

暴力枚举法是最简单的判断素数的方法,即对于n,从2到n-1依次判断是否能整除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;

}

方法二:优化暴力枚举法

虽然暴力枚举法简单易懂,但是在判断大素数时效率较低。因此可以对其进行优化,如只需要判断2到sqrt(n)之间是否有可以整除n的数即可,因为如果2到sqrt(n)之间没有可以整除n的数,则大于sqrt(n)的数也不可能整除n,如下所示:

bool isPrime(int n) {

  if (n <= 1)

    return false;

  int sqrtn = int(sqrt(n));

  for (int i = 2; i <= sqrtn; i++) {

    if (n % i == 0)

      return false;

  }

  return true;

}

方法三:埃氏筛法

埃氏筛法是一种筛选素数的方法,首先先将2到n的数全部标记为素数,再从2开始,不断将素数的倍数标记为合数,最终得到的未被标记的数即为素数。如下所示:

bool isPrime(int n) {

  if (n <= 1)

    return false;

  bool* isPrime = new bool[n + 1];

  memset(isPrime, true, sizeof(bool) * (n + 1));

  isPrime[0] = isPrime[1] = false;

  for (int i = 2; i <= n; i++) {

    if (isPrime[i]) {

      for (int j = i * 2; j <= n; j += i) {

        isPrime[j] = false;

      }

    }

  }

  bool result = isPrime[n];

  delete[] isPrime;

  return result;

}

以上三种方法均可以判断一个数是否为素数,而具体使用哪一种方法则取决于实际情况和需求。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复