大型数组筛法
想用筛法选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