C++如何求素数 |21xrx.com

C++如何求素数

2023-07-04 03:59:53 深夜i 17 0

C++ 素数求解

C++作为一门高级编程语言，可以用于解决许多数学问题，其中求素数是其中之一。所谓素数，指的是只能被1和该数本身整除的正整数，例如2、3、5、7、11等，而不包括合数，如4、6、8、9、12等。下面就介绍在C++中如何求素数。

一、暴力枚举法

暴力枚举法是一种最直接、最基础的方法，其原理是从2开始遍历到待求数n的平方根，判断是否能被整除。如果能被整除，则不是素数；如果不能被整除，则是素数。这种方法代码简单，容易理解，但是时间复杂度较高，不适用于大数据量的情况。

示例代码：

#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int n) {
  if (n <= 1) return false;
  for (int i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) return false;
  }
  return true;
}
int main() {
  int n;
  cout << "请输入一个正整数：";
  cin >> n;
  if (isPrime(n)) cout << n << "是素数";
  else cout << n << "不是素数";
  return 0;
}

二、埃氏筛法

埃氏筛法，又叫做爱氏筛法，是一种较为有效的求素数的方法。其原理是首先将待求数以及其倍数剔除，最后留下来的数即为素数。例如，如果待求数为10，则将2、4、6、8、10以及它们的倍数全部剔除，只留下3、5、7作为素数。时间复杂度比暴力枚举法低很多，但是空间复杂度较高。

示例代码：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100;
bool isPrime[N];
void Prime(int n) {
  memset(isPrime, true, sizeof(isPrime));  //将isPrime数组所有元素赋值为true
  for (int i = 2; i * i <= n; i++) {
    if (isPrime[i]) {  //如果当前数为素数
      for (int j = i * i; j <= n; j += i) {  //将其倍数设为非素数
        isPrime[j] = false;
      }
    }
  }
}
int main() {
  int n;
  cout << "请输入一个正整数：";
  cin >> n;
  Prime(n);
  for (int i = 2; i <= n; i++) {  //输出所有素数
    if (isPrime[i]) cout << i << " ";
  }
  return 0;
}

综上所述，C++求素数的方法有多种，可以根据不同的情况采用不同的算法。需要注意的是，求素数是比较基础的数学运算，需要经常练习和使用，才能掌握其原理和使用方法。

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

下一篇: 如何使用C++从文本读取字符串

评论区

相似文章