注册 登录
编程论坛 数据结构与算法

素数算法求注释

hit小龙 发布于 2012-12-29 22:31, 463 次点击
今天在网上百度了个素数求法,感觉很巧妙,很神奇,
只是能力有限,没能完全看懂。

现在分享出来,求大神帮忙写个注释,感激不尽。(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;
}
1 回复
#2
不玩虚的2013-01-03 02:36
爱拉托斯散筛法是素数检测的一种方法。具个例子,求100内的素数,先对100开方的10找出10内的素数有2,3,5,7,删去2—100内是2,3,5,7的倍数的数,剩下的就是100内的素数。具体原理是一个定理。
1