C++ 判断质数的方法 |21xrx.com

C++ 判断质数的方法

2023-07-05 10:26:29 深夜i -- --

C++ 判断质数方法

C++是一种广泛使用的编程语言，用于开发各种应用程序。在编写程序的过程中，经常需要判断一个数是否为质数。质数是只能被1和自身整除的数，比如2、3、5、7等。

在C++中，我们可以使用以下方法来判断一个数是否为质数：

1.暴力枚举法

暴力枚举法是最简单的方法，即遍历2到n-1的所有数，看是否能被n整除。如果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.优化枚举法

在暴力枚举法的基础上，我们可以对判断条件进行优化。根据小学的知识，一个数如果不是质数，那么它的因数一定是小于等于它平方根的数。因此，我们只需要遍历2到sqrt(n)的所有数即可。

示例代码：


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

3.埃氏筛法

埃氏筛法是一种筛选法，利用了质数的性质：一个数如果是质数，那么它的倍数一定不是质数。我们可以先将2到n的所有数都标记为质数，然后从小到大遍历每个质数，将它的倍数都标记为合数（即非质数）。遍历完成后，标记为质数的数即为所求。

示例代码：


bool isPrime(int n) {
  if (n <= 1) return false;
  vector<bool> primes(n + 1, true);
  for (int i = 2; i * i <= n; ++i) {
   if (primes[i]) {
     for (int j = i * i; j <= n; j += i) {
      primes[j] = false;
     }
   }
  }
  return primes[n];
}

以上就是C++判断质数的三种方法，它们各有优缺点，具体使用时可以根据实际情况选择。有了这些方法，我们可以轻松地编写出判断质数的程序。

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

下一篇: C++实现快速排序算法

评论区

()

相似文章