用欧拉筛输出1到n之间的质数
时间: 2024-05-04 13:20:18 浏览: 11
欧拉筛是一种较为高效的质数筛法,可以用来快速求解1到n之间的质数。以下是使用欧拉筛的C++代码:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int prime[N], cnt; // 存放质数的数组
bool st[N]; // st[i]表示i是否被筛掉
void get_primes(int n)
{
memset(st, 0, sizeof st);
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) prime[cnt ++ ] = i;
for (int j = 0; prime[j] <= n / i; j ++ )
{
st[prime[j] * i] = true;
if (i % prime[j] == 0) break;
}
}
}
int main()
{
int n;
cin >> n;
get_primes(n);
for (int i = 0; i < cnt; i ++ ) cout << prime[i] << " ";
cout << endl;
return 0;
}
```
在这段代码中,我们定义了一个bool类型的数组st,用来表示当前数是否被筛掉。初始时,我们将st数组全部置为false,表示所有数都没有被筛掉。然后我们从2开始枚举每一个数i,在枚举的过程中,如果当前数i还没有被筛掉,则将其加入质数数组prime中,并从2i开始,将所有i的倍数都标记为已筛掉。这里用到了一个小技巧,如果一个数k已经被标记为非质数,那么它的倍数2k, 3k, 4k...都已经被标记为非质数,因此我们只需要从k的下一个质数开始枚举即可。
最后,我们输出质数数组prime中的所有元素即可。