首页 > 其他 > 详细

0-1亿里面素数的个数

时间:2014-11-07 11:28:06      阅读:269      评论:0      收藏:0      [点我收藏+]

int sieve()

{

    unsigned int*  p=(unsigned int*)malloc(12500000);      // 一个字节8个比特位

    memset(p,-1,12500000);

    int num=100000000-2;

    for(int i=2;i<10000;i++)

    {

        if(p[i/32]&(1<<i%32))        //  判断第i位是否为1  如果为1 则表明i为素数 

        {

            for(int j=i*i;j<100000000;j+=i)           

            {

                // i的倍数为素数 ,将素数对应得比特位设为0 ,但需先判断该比特位是否为0

                 if(p[j/32]&(1<<j%32)&&num--)          //  判断第j位是否为1  如果为1 ,num减少一

                {

                        p[j/32] &=(~(1<<j%32))              //  将第j位设置为0

                }

            }

        }

    }

    free(p);

    return  num;

}

0-1亿里面素数的个数

原文:http://my.oschina.net/u/855028/blog/341762

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!