【C++练习】06.输出100以内的所有素数
目录
- 输出100以内的所有素数
- 方法1：基础判断法
- 方法2：埃拉托斯特尼筛法（效率更高）
- 方法3：优化版筛法（只考虑奇数）
- 方法4：使用STL算法
- 方法5：递归实现
- 总结：
输出100以内的所有素数
方法1：基础判断法
#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 main() {for (int i = 2; i <= 100; i++) {if (isPrime(i)) {cout << i << " ";}}return 0;
}
方法2：埃拉托斯特尼筛法（效率更高）
#include <iostream>
#include <vector>
using namespace std;void sieveOfEratosthenes(int n) {vector<bool> prime(n + 1, true);prime[0] = prime[1] = false;for (int p = 2; p * p <= n; p++) {if (prime[p]) {for (int i = p * p; i <= n; i += p) {prime[i] = false;}}}for (int p = 2; p <= n; p++) {if (prime[p]) {cout << p << " ";}}
}int main() {sieveOfEratosthenes(100);return 0;
}
方法3：优化版筛法（只考虑奇数）
#include <iostream>
#include <vector>
using namespace std;void optimizedSieve(int n) {if (n >= 2) cout << "2 ";int size = (n - 1) / 2;vector<bool> prime(size, true);for (int i = 0; i < size; i++) {if (prime[i]) {int p = 2 * i + 3;cout << p << " ";for (int j = p * p; j <= n; j += 2 * p) {prime[(j - 3) / 2] = false;}}}
}int main() {optimizedSieve(100);return 0;
}
方法4：使用STL算法
#include <iostream>
#include <vector>
#include <algorithm>
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 main() {vector<int> numbers(99);iota(numbers.begin(), numbers.end(), 2);numbers.erase(remove_if(numbers.begin(), numbers.end(), [](int n) { return !isPrime(n); }),numbers.end());for (int n : numbers) {cout << n << " ";}return 0;
}
方法5：递归实现
#include <iostream>
using namespace std;bool isPrime(int n, int i = 2) {if (n <= 2) return (n == 2);if (n % i == 0) return false;if (i * i > n) return true;return isPrime(n, i + 1);
}int main() {for (int i = 2; i <= 100; i++) {if (isPrime(i)) {cout << i << " ";}}return 0;
}
总结：
- 基础判断法简单直观，适合小范围素数判断
- 筛法在大数据量时效率更高
- STL版本展示了C++标准库的使用
- 递归版本展示了另一种思维方式
输出结果都是100以内的素数：
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