身上无钱你莫邪

moye's c++ blog

c++ 位集计算素数法

位集(bitset)计算是用空间换时间,这里的例子是书上的,计算1亿内的所有素数个数:

#include<iostream>
#include
<bitset>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
    
/*位集 计算1亿内的所有素数*/
    bitset
<100000000>*= new bitset<100000000>;
    p
->set();
    
for(int i=2;i<=10000;++i)
        
if(p->test(i))
            
for(int j=i*i;j<p->size();j+=i)
                p
->reset(j);
    
int num=0;
    
for(int i=2;i<100000000;++i)
        
if(p->test(i)){
            cout
<<i<<( num%9==0 ?"\n":" ");
            num
++;
        }
    cout
<<"Prime's count:"<<num<<endl;
    delete[]p;
    system(
"pause");
    
return 0;
}

可将
cout<<i<<(num%9==0?"\n":" ");
这一行去除,输出太耗时,呵呵。

posted on 2008-12-18 10:39 莫耶 阅读(517) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


公告

导航

<2008年12月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

统计

常用链接

留言簿(3)

随笔档案

友情链接

搜索

最新评论

阅读排行榜

评论排行榜