C++寻找不小于m的最小素数 |21xrx.com

C++寻找不小于m的最小素数

2023-07-13 13:20:44 深夜i -- --

C++ 搜寻不小于m 最小素数

在C++编程中，寻找不小于m的最小素数是一个常见的问题。素数是指只能被1和本身整除的自然数，因此寻找最小的素数需要在可接受的时间内枚举自然数并判断其是否为素数。在本文中，我们将介绍两种不同的方法来解决这个问题。

第一种方法是暴力枚举。我们可以从m开始，依次遍历自然数并判断其是否为素数。判断素数的方法是：对于每个自然数i，从2到i-1依次判断i是否能被整除。如果i不能被整除，则i为素数。这种方法虽然可行，但随着m的增大，时间复杂度会快速增加，因此不适用于大数据量的处理。

第二种方法是使用质数筛法。质数筛法是一种优化的素数查找方法，最常见的实现方式是Eratosthenes筛法。这个算法通过不断筛选出素数的倍数来确定素数，从而极大地提高了计算效率。具体实现方式是：首先从2开始，标记它的所有倍数为合数；然后从3开始，如果一个数没有被标记为合数，则它为素数。这个方法的时间复杂度为O(nloglogn)，可以处理更大的数据量。

下面是C++代码实现：

第一种方法：


#include <iostream>
using namespace std;
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;
}
int findPrime(int m) {
  int i = m;
  while (!isPrime(i)) i++;
  return i;
}
int main() {
  int m;
  cin >> m;
  cout << findPrime(m) << endl;
  return 0;
}

第二种方法：


#include <iostream>
#include <vector>
using namespace std;
vector<bool> prime;
void sieve(int n) {
  prime.resize(n+1, true);
  prime[0] = prime[1] = false;
  for (int i = 2; i*i <= n; i++) {
    if (prime[i]) {
      for (int j = i*i; j <= n; j += i) {
        prime[j] = false;
      }
    }
  }
}
int findPrime(int m) {
  while (true) {
    if (prime[m]) return m;
    m++;
  }
}
int main() {
  int m;
  cin >> m;
  sieve(m);
  cout << findPrime(m) << endl;
  return 0;
}

无论使用哪种方法，我们都可以求出不小于m的最小素数。在实际开发中，我们应根据数据量和运行效率选择合适的方法来处理。

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

下一篇: C++程序为什么无法打开命令提示符？

评论区

()

相似文章