#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性能测试工具
sIEve-0.0.8(IE Sieve_检测IE内存泄露情况)
ExtJS内存调试工具 sIEve,extjsIE工具。
sieve-A Password Manager App, showcasing some common Android vulnerabilities drozer是一款针对Android系统的安全测试框架。Drozer可以通过与Dalivik VM,其它应用程序的IPC端点以及底层操作系统的交互,避免正...
siege is a small password manager app created to showcase some of the common vulnerabilities found in android applications(sieve是一款小型密码管理软件,用来展示android应用程序中常见的一些漏洞)
sIEve-0.0.8 界面汉化 界面预览:http://blog.csdn.net/z3642214/article/details/7056238
sIEve可以有效帮助您监控javascript内存,以协助解决内存泄漏问题。
sieve, 雷鸟筛选插件 Thunderbird Sieve是服务器端邮件过滤功能的强大脚本语言。 它的目的是与 IMAP,因此它被广泛扩展。 许多IMAP服务器都能够运行筛选过滤器。 筛选器在服务器端存储并运行所有脚本。现在有一个...
IE内存泄漏检测工具。 个人用过 感觉不错。
这是一款绿色软件,无需安装,内部嵌入了一个IE 浏览器控件,用户可以通过该控件访问需要测试的网页。
目的:为建筑物选址提供合适区域的视觉表示; 这是为了降低通常与环境因素相关的建设成本,使用ArcGIS 10.1的空间分析工具来叠加地图层的约束和准则。方法/统计分析:本研究采用地理信息系统(GIS)筛选方法,选择...
原油资源分数较高,现在换成一个新的,帮助更多的人利用改工具学习。去掉.1
js开发对于dom操作,IE可能会IE内存泄漏,sIEve-0.0.8工具会监控内存使用和泄漏情况
资源分类:Python库 所属语言:Python 资源全名:primesieve-1.4.1-cp35-cp35m-win32.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
总理筛 primesieve是一个命令行程序和C / C ++库,用于快速生成素数。 它具有非常高的缓存效率,它可以检测CPU的L1和L2缓存大小并相应地分配其主要数据结构。 默认情况下,它也是多线程的,它尽可能使用所有可用的...
sIEve 界面很简单,左侧:内嵌了一个浏览器控件,我可以访问任何网址,下方还有个内存检查,这样我们可以方便看出内存的升降情况以及dom使用数量曲线。 右侧面板,我们可以通过 Show in use 看到目前页面使用的dom...
NFS的具体介绍和实现,内容非常的全,要学习NFS的看完后应该就无敌了
NULL 博文链接:https://softwarexiang120.iteye.com/blog/1917669
:alembic: Sieve是.NET Core的一个简单,干净且可扩展的框架,它开箱即用地添加了排序,筛选和分页功能。 最常见的用例是服务ASP.NET Core GET查询。 ASP.NET Core的用法 在此示例中,考虑具有Post实体的应用。 GET...
筛sieve是erlang中使用连接处理的简单TCP路由代理(第7层)。 它使您可以在Erlang中配置例程逻辑。 如果您需要根据传输的内容来代理与不同后端服务器的连接,那么sieve将为您提供帮助。 它是proxymachine的。建造您...