筛法素数产生器

[c]代码库

/*筛法素数产生器
语法：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;
}