C++实现求1到100的质数：三种循环方式 |21xrx.com

C++实现求1到100的质数：三种循环方式

2023-07-05 00:04:57 深夜i -- --

C++ 质数循环方式 1-100 实现

C++作为一种高效的编程语言，被广泛应用于计算机科学和工程领域。求1到100的质数是一个经典的编程问题，本文将介绍使用C++实现求1到100的质数的三种循环方式。

首先，我们需要了解什么是质数。质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。例如，2、3、5、7等都是质数。

方法1：暴力枚举法

暴力枚举法是一种简单粗暴的方法，它的思路是对每一个自然数n，从2到n-1检查是否能整除它，如果能，则它不是质数。代码实现如下：


#include<iostream>
using namespace std;
bool isPrime(int n) {
  for (int i = 2; i < n; i++) {
    if (n % i == 0)
      return false;
    
  }
  return true;
}
int main() {
  for (int i = 2; i <= 100; i++) {
    if (isPrime(i))
      cout << i << " ";
    
  }
  return 0;
}

输出结果为：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

方法2：优化枚举法

虽然暴力枚举法是最简单的方法，但是它的效率很低。我们可以进行一些优化，例如，从2到n/2检查是否能整除它，如果没有就说明它是质数。代码实现如下：


#include<iostream>
using namespace std;
bool isPrime(int n) {
  for (int i = 2; i <= n / 2; i++) {
    if (n % i == 0)
      return false;
    
  }
  return true;
}
int main() {
  for (int i = 2; i <= 100; i++) {
    if (isPrime(i))
      cout << i << " ";
    
  }
  return 0;
}

输出结果与方法1相同。

方法3：埃拉托色尼筛法

埃拉托色尼筛法是一种高效的求质数方法，它的思路是将不是质数的数筛掉，最终留下的就是质数。具体实现可以用一个布尔类型的数组来表示数字是否是质数，初始时全部赋值为true，然后对于每个质数p，将从p*p开始的p的倍数都标记为false，这些数就不是质数了。代码实现如下：


#include<iostream>
using namespace std;
int main() {
  bool isPrime[101] = { true };
  for (int i = 2; i <= 100; i++) {
    if (isPrime[i]) {
      cout << i << " ";
      for (int j = i * i; j <= 100; j += i) {
        isPrime[j] = false;
      }
    }
  }
  return 0;
}

输出结果与方法1和2相同。

总结

本文介绍了使用C++实现求1到100的质数的三种循环方式，它们分别是暴力枚举法、优化枚举法和埃拉托色尼筛法。它们的效率逐步提高，埃拉托色尼筛法是最高效的一种方法。在实际应用中，应根据实际问题选择适合的算法。

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

下一篇: C++学习多久适合参加奥赛？

评论区

()

相似文章