/*筛法素数产生器 |
语法:result=prime(int a[],int n); |
参数: |
a[]: 用于返回素数的数组 |
n: 产生n以内的素数,按升序放入a[]中 |
返回值: n以内素数的个数 |
注意: |
其中W[],B[]已知,W[i]>0且W[i]与W[j]互质, 求a |
*/ |
int prime ( int a[], int n ) |
{ |
int i,j,k,x,num,*b; |
n++; |
n/=2; |
b= ( int * ) malloc ( sizeof ( int ) * ( n+1 ) *2 ); |
a[0]=2; |
a[1]=3; |
num=2; |
for ( i=1; i<=2*n; i++ ) |
b[i]=0; |
for ( i=3; i<=n; i+=3 ) |
for ( j=0; j<2; j++ ) |
{ |
x=2* ( i+j )-1; |
while ( b[x]==0 ) |
{ |
a[num++]=x; |
for ( k=x; k<=2*n; k+=x ) |
b[k]=1; |
} |
} |
return num; |
} |