方法一：
简单易懂
View Code
1 const int maxn = 10005 ; 2 int prime[ maxn ],shu[ maxn ]; 3 void get_prime(){ 4 for( int i=1;i<maxn;i+=2 ) shu[ i ]=1; 5 for( int i=0;i<maxn;i+=2 ) shu[ i ]=0; 6 shu[ 1 ]=0,shu[ 2 ]=1; 7 for( int i=3;i<maxn;i+=2 ){ 8 if( shu[ i ]==1 ){ 9 int t,delta; 10 delta=i*2; 11 t=delta+i; 12 while( t<maxn ){ 13 shu[ t ]=0; 14 t+=delta; 15 } 16 } 17 } 18 prime[ 1 ]=2; 19 int cnt=2; 20 for( int i=3;i<(int)(sqrt(maxn*1.0));i++ ){ 21 if( shu[ i ]==1 ) prime[ cnt++ ]=i; 22 } 23 }