今天在网上百度了个素数求法，感觉很巧妙，很神奇，
只是能力有限，没能完全看懂。

现在分享出来，求大神帮忙写个注释，感激不尽。（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;
}

真的很晦涩，看了一小时了，我怎么感觉这个代码有唬人的成分啊

猫哥
可是它真心能解出来啊……

貌似是素数筛选法

我没说算不出来啊，我是说那多位移吓唬人，直接乘除就好了啊

额
好吧。

我看到位运算也是头大

求大神指点啊

有点晕，好像求素数没那么夸张啊！！以前写的感觉很简单啊！

这个优化的啊
10亿内只要13秒

有人看的懂么……

郁闷了

有点意思。算法并不复杂，只不过代码写的呵呵。

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

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