#include <iostream>#include <set>using namespace std;#include "IO.hpp"void SIEVE(set<int>& primes,int limit){ int index; primes.erase(primes.begin(),primes.end()); for(int i=2;i<limit;i++) primes.insert(i); for(int i=2;i*i<=limit;i++) if(primes.find(i) != primes.end()){ index = 2*i; while(index <= limit){ primes.erase(index); index += i; } } return;}int main(int argc,char *argv[]){ set<int> primeSet; set<int>::iterator iter; int primeLimit,count=0; cout<<"Enter upper limit for the set of primes: "; cin>>primeLimit; cout<<endl; SIEVE(primeSet,primeLimit); iter= primeSet.begin(); writeContainer(primeSet.begin(),primeSet.end()," ",10); cout<<endl; return 0;}
#ifndef _IO_HPP_#define _IO_HPP_#include <vector>#include <set>#include <list>using namespace std;//LINE=0 不需换行//separator 表示每个元素间隔符号//N为元素个数//writeArray (arr[], N:, separator, LINE)//writeContainer (begin(), end(), separator, LINE)//writeVector (vector<T>, separator, LINE)//writeList (list<T>, separator, LINE)//writeSet (set<T>, separator, LINE)template <typename T>void writeArray(const T arr[], \ int N, \ const char* separator, \ int LINE){ for(int i=0;i<N;i++){ cout<<arr[i]<<separator; if(LINE!=0) if(i%LINE==0) cout<<endl; } cout<<endl; return;}template <typename T>void writeVector(const vector<T>& v, \ const char* separator, \ int LINE){ int i, n = v.size(); for(i=0;i<n;i++){ cout<<v[i]<<separator; if(LINE!=0) if(i%LINE==0) cout<<endl; } cout<<endl; return;}template <typename T>void writeList(const list<T>& alist, \ const char* separator, \ int LINE){ typename list<T>::const_iterator iter; int count = 0; iter = alist.begin(); while(iter != alist.end()){ count++; cout<<*iter<<separator; if(LINE!=0) if(count%LINE==0) cout<<endl; iter++; } cout<<endl; return;}template <typename T>void writeSet(const set<T>& alist, \ const char* separator, \ int LINE){ typename set<T>::const_iterator iter; int count = 0; iter = alist.begin(); while(iter != alist.end()){ count++; cout<<*iter<<separator; if(LINE!=0) if(count%LINE==0) cout<<endl; iter++; } cout<<endl; return;}template <typename Iterator>void writeContainer(Iterator begin, \ Iterator end, \ const char* separator, \ int LINE){ Iterator iter = begin; int count = 0; while (iter!=end){ count++; cout<<*iter<<separator; if(LINE!=0) if(count%LINE==0) cout<<endl; iter++; } cout<<endl; return;}#endif
这个筛实现很简单, 比如上限是300 就把300以内所有小于sqrt(300)质数的倍数划掉就行, 我这里划了小于sqrt(300)所有数的倍数, 因为要划小于sqrt(300)的质数必须先生成, 用两此筛就行
比如筛10000以内 先生成100以内的质数 然后划掉100以内的质数就可以,不用划100个数字,会节约点时间
按照SPOJ上的提示,用筛法,二次筛 都无法通过SPOJ第二题, 都是超时.
或许我筛法写得性能不好 像set容器 性能可能确实有问题
相关资源：Sieve.apk漏洞联系工具
