素数求法求注释。
今天在网上百度了个素数求法,感觉很巧妙,很神奇,只是能力有限,没能完全看懂。
现在分享出来,求大神帮忙写个注释,感激不尽。(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;
}