题目

{% raw %}

点击显/隐题目
{% endraw %} 用筛选法求(1,n]之内的全部素数

{% raw %}



{% endraw %}

行1：一个整数n，n∈[2,100000]

{% raw %}



{% endraw %}

每行输出一个素数，由小到大排列

{% raw %}





{% endraw %}

20

{% raw %}



{% endraw %}

2
3
5
7
11
13
17
19

{% raw %}




{% endraw %}

题解

算法模板题

筛法求素数

直接套用模板即可

代码

点击显/隐代码
```cpp 求素数 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份 /*/ #define debug #include //*/ #include #include #include #include using namespace std;

const int maxn = 100005;
bool is_prime[maxn+1];

int main(){
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(0);

int n;
cin >> n;

int m=sqrt(n+0.5);
memset(is_prime,true,sizeof(is_prime));
for(int i=2;i<=m;i++){
    if(is_prime[i]){
        for(int j=i*i;j<=n;j+=i){
            is_prime[j]=false;
        }
    }
}
for(int i=2;i<=n;i++){
    if(is_prime[i]==true){
        cout<<i<<endl;
    }
}



#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;

}

</div>