C++如何判断一个数是否为质数 |21xrx.com

C++如何判断一个数是否为质数

2023-07-04 19:29:02 深夜i -- --

C++ 判断数质数

质数是自然数中除了1和本身之外不再有其他因数的数，如2、3、5、7、11等。在编程中，判断一个数是否为质数是一个常见的问题，特别是在加密和密码学中。

C++实现判断一个数是否为质数，可以使用以下两种方法：

方法一：暴力法（Brute Force）

暴力法是最简单的方法，它从2开始遍历到该数的平方根，逐个判断该数是否能被整除。如果找到一个因数，那么该数就不是质数。否则，该数就是质数。实现如下：


bool isPrime(int number) {
 if (number <= 1) // 质数定义：大于1的自然数
  return false;
 
 for (int i = 2; i * i <= number; i++) { // i遍历到该数的平方根
  if (number % i == 0) 不是质数
   return false;
  
 }
 return true; // 否则为质数
}

方法二：艾拉托色尼筛法（Sieve of Eratosthenes）

艾拉托色尼筛法是一种比较高效的算法，它利用了质数的定义，将一定范围内的所有质数筛选出来。具体实现如下：


const int MAX = 1000000; // 最大范围
bool isPrime[MAX + 1]; // 标记是否为质数
void sieve() {
 memset(isPrime, true, sizeof(isPrime)); // 先全部标记为质数
 isPrime[0] = false; // 0和1不是质数
 isPrime[1] = false;
 for (int i = 2; i * i <= MAX; i++) { // i遍历到最大范围的平方根
  if (isPrime[i]) { // 如果i是质数，则将i的倍数标记为非质数
   for (int j = i * i; j <= MAX; j += i) {
    isPrime[j] = false;
   }
  }
 }
}
bool isPrime(int number) {
 if (number <= 1) // 质数定义：大于1的自然数
  return false;
 
 return isPrime[number]; // 直接查表判断是否为质数
}

使用艾拉托色尼筛法的优点是可以在一定范围内快速查找多个数的质数性，不需要每次都用暴力法重新计算，而且可以用空间换时间，将质数的表存储下来，方便快捷。

综上所述，以上是C++判断一个数是否为质数的两种常用方法，具体选择哪种方法取决于数据量和时间要求等因素。

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

下一篇: C++中status的作用是什么？

评论区

()

相似文章