sailing
  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  1 Posts :: 4 Stories :: 0 Comments :: 0 Trackbacks

常用链接

留言簿(10)

我参与的团队

随笔档案

文章档案

搜索

  •  

最新评论

求素数算法-空间优化（代码原创-通过测试）

穷举法求某个数是否是素数：用n除以1~sqrt(n)里面的每一个数。如果找不到能除尽的数，那么n就是素数。
代码好简单，略。

筛选法求1~N范围内的素数：
1.先找到第一个素数p
2.去除p的倍数，既非素数
3.在剩下的数里面找到大于p的最小的数，它也是素数，用它更新p，重复2，3，直到到达N.

0~1亿以内的素数个数，Time cost(milli-second)
Numbers of primes in 1~100=25      Time cost=0
Numbers of primes in 1~1000=168      Time cost=0
Numbers of primes in 1~10000=1229      Time cost=0
Numbers of primes in 1~100000=9592      Time cost=7
Numbers of primes in 1~1000000=78498      Time cost=53
Numbers of primes in 1~10000000=664579      Time cost=502
Numbers of primes in 1~100000000=5761455      Time cost=8665
Press any key to continue . . .


空间未优化的代码：（代码原创，通过测试 ）
int primeNum(int upperLimits)
{
    unsigned int *pArr=new unsigned int[upperLimits+1];
    memset(pArr,0,(1+upperLimits)*sizeof(int));
    for(unsigned int i=0; i<=upperLimits; ++i)
    {
        pArr[i]=i;
    }
    register int i=2;
    while(i<upperLimits/2)
    {
        register int k=2;
        //(1)
        while(k*i<=upperLimits)
        {
            pArr[k*i]=0;
            ++k;
        }
        ++i;
        //(2)
        while(i<upperLimits/2 && pArr[i]==0)
        {
            ++i;
        }
    }
    int n=0;
    for (int i=2;i<upperLimits; ++i)
    {
        if(pArr[i]!=0)
        {
            //cout<<pArr[i]<<" ";
            ++n;    
        }
    }
    cout<<endl<<"number="<<n<<endl;

    delete []pArr;
    return 0;

}


空间优化后的代码：（原创，通过测试）
用位(bit)记录1~N的每一个数。对于32位整型数来说，可以将空间复杂度降到原来的1/32。
 1int primeNumber(int upperLimitNum)
 2{
 3    int limit=upperLimitNum;
 4    unsigned int IntBits=8*sizeof(unsigned int);
 5    unsigned int nInt=ceil(((double)limit+1.0)/IntBits);
 6    unsigned int *pArr=new unsigned int[nInt];
 7    //先将所有位置0，表示全都是素数。然后找出合数，将合数对应位置1。
 8    for(int i=0; i<nInt; ++i) pArr[i]= 0UL;
 9    
10    register unsigned int j=2;
11    register int whichInt,whichBit;
12    while(j<=limit/2)
13    {
14         register int k=2;
15        //剔除素数的倍数，2倍，3倍，4倍.
16        while(k*j<=limit)
17        {
18            whichInt=(k*j-1)/IntBits;
19            whichBit=(k*j-1)%IntBits;//shift whichBit 
20            //非素数的对应位 置1。比如，4不是素数，将UINT里面从前往后数到第4位，该位置1.
21            pArr[whichInt]=pArr[whichInt] | (1UL <<(IntBits-whichBit-1) ) ;
22            ++k;
23        }
24        ++j;
25
26        //寻找下一个素数：
27        //既，剔除非素数后（被置1）,剩下的数里面最小的那个数。
28        //如，2 是素数，剔除2的倍数468后，剩下的里面最小的是3，就是下一个素数
29        whichInt=(j-1)/IntBits;            //找到这个数对应的位在哪个UINT里面。
30        whichBit=(j-1)%IntBits;            //找到这个数对应的位在某个UINT里面的哪一位。
31        bool bitset=(pArr[whichInt] & 1UL<<(IntBits-whichBit-1));//如果这一位是1，既bitset=1，表示不是素数。
32        while(j<=limit/2 &&  bitset    )    //既然不是素数，那我们就继续找，一直找到下一个素数，停止。
33        {
34            ++j;
35            whichInt=(j-1)/IntBits;
36            whichBit=(j-1)%IntBits;
37            bitset=(pArr[whichInt] & 1UL<<(IntBits-whichBit-1));
38        }//循环结束后的j值就是下一个素数
39
40    }//剔除j的倍数，并继续寻找下一个素数。
41
42    int i=2;
43    int nprime=0;
44    while(i<=limit)
45    {
46        whichInt=(i-1)/IntBits;
47        whichBit=(i-1)%IntBits;
48        if( !(pArr[whichInt] & (1UL<<IntBits-whichBit-1)) )
49        {
50            cout<<i<<" ";
51            ++nprime;
52        }
53        ++i;
54    }
55    cout<<endl<<"nprime="<<nprime<<endl;
56
57
58
59    delete []pArr;
60    return nprime;
posted on 2009-10-09 02:59 sailing 阅读(493) 评论(0)  编辑 收藏 引用

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