| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1798 人关注过本帖, 2 人收藏
标题:素数求法求注释。
只看楼主 加入收藏
hit小龙
Rank: 6Rank: 6
等 级:侠之大者
帖 子:173
专家分:462
注 册:2012-12-6
结帖率:100%
收藏(2)
已结贴  问题点数:30 回复次数:32 
素数求法求注释。
今天在网上百度了个素数求法,感觉很巧妙,很神奇,
只是能力有限,没能完全看懂。

现在分享出来,求大神帮忙写个注释,感激不尽。(ps:最好写详细点)
#include <stdio.h>
#include <time.h>
#include <math.h>
#define SIZE 1000000000


#define BITMAPSIZE 8
unsigned char map[SIZE / 2 / BITMAPSIZE + 1];
unsigned char bsm[10000];/* 这是一个估算值 */
int bn[10000];

int main()
{
    int i, j, l;
    int c = 0;
    int st;
    int basn;

    st = clock();

 /* 计算素数 */
    basn = (int)sqrt(SIZE) + 1;
    for (i = 3; ; i += 2)
    {
        if ((bsm[i / BITMAPSIZE] & (1 << (i % BITMAPSIZE))) == 0)
        {
            for (j = i << 1; j < basn; j += i)
            {
                bsm[j / BITMAPSIZE] |= (1 << (j % BITMAPSIZE));
            }
            bn[c++] = i;
            if (i > basn)
                break;
        }
    }


    for (i = 0; i < c; i++)
    {
        j = bn[ i ] << 1;
        l = j + bn[ i ];
        do
        {
            map[l / (BITMAPSIZE * 2)] |= (1 << ((l >> 1) % BITMAPSIZE));
            l += j;
        } while (l < SIZE);
    }
    c = 0;
    for (i = 1; i < SIZE / 2; i++)
    {
        i++;
        if ((map[i / BITMAPSIZE] & (1 << (i % BITMAPSIZE))) == 0)
        {
            c++;
        }
        i++;
        if ((map[i / BITMAPSIZE] & (1 << (i % BITMAPSIZE))) == 0)
        {
            c++;
        }
    }


    printf("1~1000000000 number: %d\n", c);

    return 0;
}
搜索更多相关主题的帖子: clock 分享 include 百度 能力 
2012-12-29 15:37
yaobao
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:蒙面侠
威 望:4
帖 子:1854
专家分:4121
注 册:2012-10-25
收藏
得分:5 
真的很晦涩,看了一小时了,我怎么感觉这个代码有唬人的成分啊

认认真真的学习,踏踏实实的走路:戒骄戒躁!!!
2012-12-29 17:14
hit小龙
Rank: 6Rank: 6
等 级:侠之大者
帖 子:173
专家分:462
注 册:2012-12-6
收藏
得分:0 
回复 2楼 yaobao
猫哥
可是它真心能解出来啊……
2012-12-29 17:21
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
貌似是素数筛选法

                                         
===========深入<----------------->浅出============
2012-12-29 17:22
yaobao
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:蒙面侠
威 望:4
帖 子:1854
专家分:4121
注 册:2012-10-25
收藏
得分:0 
我没说算不出来啊,我是说那多位移吓唬人,直接乘除就好了啊

认认真真的学习,踏踏实实的走路:戒骄戒躁!!!
2012-12-29 18:10
hit小龙
Rank: 6Rank: 6
等 级:侠之大者
帖 子:173
专家分:462
注 册:2012-12-6
收藏
得分:0 
回复 5楼 yaobao

好吧。

我看到位运算也是头大
2012-12-29 18:11
hit小龙
Rank: 6Rank: 6
等 级:侠之大者
帖 子:173
专家分:462
注 册:2012-12-6
收藏
得分:0 
求大神指点啊
2012-12-29 23:02
聊斋唐少
Rank: 2
等 级:论坛游民
帖 子:17
专家分:11
注 册:2012-12-26
收藏
得分:0 
有点晕,好像求素数没那么夸张啊!!以前写的感觉很简单啊!
2012-12-29 23:13
hit小龙
Rank: 6Rank: 6
等 级:侠之大者
帖 子:173
专家分:462
注 册:2012-12-6
收藏
得分:0 
回复 8楼 聊斋唐少
这个优化的啊
10亿内只要13秒

有人看的懂么……

郁闷了
2012-12-29 23:14
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:25 
有点意思。算法并不复杂,只不过代码写的呵呵。

本质就是素数筛,只不过用了两遍。
第一组循环统计根号十亿内的素数。正常的筛法应用。
第二组循环用上面计算出来的素数筛剩余的范围。
这里比较有意思的地方就是它节省内存用的技巧。1.使用位作标志。2.它删掉了所有的偶数。也就是说第1位表示3,第2位表示5等等。也正因如此它的筛的步长才是两倍的素数,而起始步长是3倍的素数。
第三组循环就是统计标志位了。

写的挺复杂,但我很怀疑它的效率比只用一次筛能好多少,明天有时间我倒试一下。手机上看的,打字也不方便,就解释这么多吧。还有,它的输出结果应该是错的,我没看到它有统计2这个唯一的偶素数。解决办法可以在最后一组循环时将c初始化为1,或让i从0开始循环。我个人喜欢后一种,它更有意义。

重剑无锋,大巧不工
2012-12-30 00:08
快速回复:素数求法求注释。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.025893 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved