核心思想: 从 i=2 开始, 划去 i 的倍数, 即剩下 i 为质数 (如删去 2 的倍数后 2 为质数, 再删去 3 的倍数后 3 为质数, 4 被删除则跳过, 5 未被删除则记录然后删除 5 的倍数... 以此类推)
- #include <bits/stdc++.h>
- using namespace std;
- #define max_n 1000000
- int prime[max_n]={0};
- bool is_prime[max_n];
- int sieve/* 埃氏筛选 */(int n) {
- int p=0;
- memset(is_prime,1,sizeof(is_prime));
- for(int i=2;i<=n;i++) {
- if(is_prime[i]) {
- prime[p]=i;
- p++;
- for(int j=i*2;j<=n;j+=i) {
- is_prime[j]=0;
- }
- }
- }
- return p;
- }
- int main() {
- int n;
- cin>>n;
- int p=sieve(n);
- for(int i=0;i<p;i++) {
- cout<<prime[i]<<" ";
- }
- }
来源: http://www.bubuko.com/infodetail-3341936.html