21xrx.com
2024-12-22 22:34:30 Sunday
登录
文章检索 我的文章 写文章
C++中如何判断一个数字是否为素数
2023-06-28 16:40:26 深夜i     --     --
C++ 判断 数字 素数

在C++中,判断一个数字是否为素数的方法有很多种,其中最常用的方法是试除法。

试除法的基本思想是:判断一个数n是否为素数,只需从2开始循环到n-1,分别用n除以每个循环到的数,若能整除则n不是素数,若到了n-1也没有被整除,则n是素数。

具体实现方法如下:


bool isPrime(int n) {

  if (n <= 1)  // 特判1及小于1的数

    return false;

  

  for (int i = 2; i <= sqrt(n); i++) { // 试除法

    if (n % i == 0)  // 如果能整除

      return false; // 则不是素数

    

  }

  return true; // 不被2到sqrt(n)内的任何一个数整除,则是素数

}

代码中,先判断n是否小于等于1,若是,则直接返回false。否则,从2到sqrt(n)(因为大于sqrt(n)的数肯定不能整除n)进行循环,判断是否能被n整除,若能则返回false,否则继续循环。最后,如果在2到sqrt(n)内都没有找到能整除n的数,则n是素数,返回true。

需要注意的是,由于n是int类型,因此循环到sqrt(n)即可,否则会因为溢出出现错误。

判断一个数字是否为素数是C++中非常基础的问题,掌握这个问题的解答可以为日后的编程打下坚实的基础。

  
  

评论区

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