首页c++用筛法求素数的方法，求100以内的素数。

c++用筛法求素数的方法，求100以内的素数。

时间: 2024-12-14 16:14:21 浏览: 42

在C++中，我们可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）来找出100以内的素数。这是一种简单而高效的算法，通过维护一个布尔数组，标记出非素数的位置。以下是基本的步骤： 1. 创建一个大小为101的布尔数组isPrime，初始化所有元素为true，因为最初假设100以内所有的数字都是素数。 2. 遍历数组，从第一个未标记的素数2开始（素数的第一个元素），将它的所有倍数标记为非素数（即设置对应的isPrime[i*2]、isPrime[i*3]...等为false）。这是因为除了1和本身外，一个数如果有其他因子，那么这个因子一定比它小。 3. 继续寻找下一个未被标记为非素数的数字，直到遍历到√100（约等于10）。因为如果一个数大于10并且不是素数，那么它必定有一个因数小于或等于它的平方根。 4. 最后，所有isPrime数组中值为true的索引就是100以内的素数。下面是简单的C++代码实现： ```cpp #include <iostream> #include <cmath> using namespace std; void sieveOfEratosthenes(int n) { bool isPrime[n+1]; memset(isPrime, true, sizeof(isPrime)); for (int p=2; p*p<=n; p++) { if (isPrime[p]) { for (int i=p*p; i<=n; i += p) isPrime[i] = false; } } for (int p=2; p<=n; p++) if (isPrime[p]) cout << p << " "; } int main() { int limit = 100; cout << "100以内的素数有: "; sieveOfEratosthenes(limit); return 0; } ``` 当运行此程序时，它会打印出100以内的所有素数。

阅读全文