<h1 id="heading">题目</h1>
<p>{% raw %}</p>
<div><div class="fold_hider"><div class="close hider_title">点击显/隐题目</div></div><div class="fold">
    <div class="oj">   
        <div class="part" title="Description">
{% endraw %}
用筛选法求(1,n]之内的全部素数  
<p>{% raw %}<br>
</div><br>
<div class="part" title="Input"><br>
{% endraw %}</p>
<p>行1：一个整数n，n∈[2,100000]</p>
<p>{% raw %}<br>
</div><br>
<div class="part" title="Output"><br>
{% endraw %}</p>
<p>每行输出一个素数，由小到大排列</p>
<p>{% raw %}<br>
</div><br>
<div class="samp"><br>
<div class="clear"></div><br>
<div class="input part" title="Sample Input"><br>
{% endraw %}</p>
<p>20</p>
<p>{% raw %}<br>
</div><br>
<div class="output part" title="Sample Output"><br>
{% endraw %}</p>
<p>2<br>
3<br>
5<br>
7<br>
11<br>
13<br>
17<br>
19</p>
<p>{% raw %}<br>
</div><br>
<div class="clear"></div><br>
</div><br>
</div></p>
</div></div>
{% endraw %}

<h1 id="heading-1">题解</h1>
<p>算法模板题</p>
<p><a href="/post/Algorithm/Prime.html">筛法求素数</a></p>
<p>直接套用模板即可</p>
<h1 id="heading-2">代码</h1>
<div><div class="fold_hider"><div class="close hider_title">点击显/隐代码</div></div><div class="fold">```cpp 求素数 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
/*/
#define debug
#include <ctime>
//*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
<p>const int maxn = 100005;<br>
bool is_prime[maxn+1];</p>
<p>int main(){<br>
#ifdef debug<br>
freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);<br>
int START = clock();<br>
#endif<br>
cin.tie(0);<br>
cin.sync_with_stdio(0);</p>
<pre><code>int n;
cin &gt;&gt; n;

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



#ifdef debug
printf(&quot;Time:%.3fs.\n&quot;, double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
</code></pre>
<p>}</p>
<pre style="background-color:#fff">&lt;/div&gt;</pre>

AOJ 483.求素数