/*
筛选法求(1~n)素数
分析:由希腊著名数学家埃拉托色尼提出的所谓“筛法”,步骤如下:
①将所有候选数放入筛中;
②找筛中最小数(必为素数)next,放入集合primes中;
③将next的所有倍数从筛中筛去;
④重复②~④直到筛空。编程时,用集合变量sieve表示筛子,用集合primes存放所有素数。
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<vector>
int main()
{
int i,j,n,minum;
std::vector<int> primes;
std::vector<int> sieve;
std::vector<int>::iterator it;
scanf("%d",&n);
for(i=2;i<n;i++){
sieve.push_back(i);
}
while(sieve.size()){
minum=sieve[0];
for(i=0;i<sieve.size();i++){
if(minum>sieve[i]){
minum=sieve[i];
}
}
primes.push_back(minum);
for(it=sieve.begin();it!=sieve.end();){
if(*it%minum==0){
it=sieve.erase(it);
}else{
++it;
}
}
}
std::cout<<"result=";
for(i=0;i<primes.size();i++){
std::cout<<" "<<primes[i];
}
return 0;
}