大型数组筛法
想用筛法选10^8内素数,但定义10^8元素的数组用常规求小数组的筛法无法成功运行,请教如何用定义大型数组用筛法
其中2的倍数就不要存了,数量一下子就少了一半
因为状态只有“是 和 否”,1bit就够了,那么只需要 10^8/2/8 个字节,不足 6M Bytes
程序代码:#include <stdio.h>
#include <stdlib.h>
#define N 100000000u
int main()
{
#define UINT_NUM ( ((N)-1)/2 + sizeof(unsigned)*8-1 )/(sizeof(unsigned)*8)
#define GET_BITVALUE(p,idx) (((p)[((idx)/2-1)/(sizeof(unsigned)*8)]>>(((idx)/2-1)%(sizeof(unsigned)*8)))&1)
#define SET_BITVALUE(p,idx) ((p)[((idx)/2-1)/(sizeof(unsigned)*8)] |= 1u<<(((idx)/2-1)%(sizeof(unsigned)*8)))
unsigned* p = (unsigned*)calloc( UINT_NUM, sizeof(unsigned) );
printf( "2" );
for( unsigned i=3; i<=N; i+=2 )
{
if( GET_BITVALUE(p,i) )
continue;
printf( " %u", i );
for( unsigned j=3*i; j<=N; j+=2*i )
SET_BITVALUE(p,j);
}
free( p );
return 0;
}一共5761455个质数,最大的一个是99999989