sieve5.c

该程序用于在一个给定的数组中寻找素数

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
//#define getisp(i) (isprime[(i)/8]>>((i)%8))&0x1
/*
#define setisp(i,j) j?\
(isprime[(i)/8]|=(0x1<<((i)%8))):\
(isprime[(i)/8]&=~(0x1<<((i)%8)))
*/
#define getisp(i) (isprime[(i)>>3]>>((i)&0x7))&0x1

int main(int argc, char *argv[])
{
        int max = 100;                           // Assign a default value
				max =abs(atoi(argv[1]));
        // Create an array that specifies whether each number is prime or not.
        int maxhalf=(max+1)/2;
        unsigned char* isprime= (unsigned  char*)malloc(maxhalf/8+2); //only save odd
        int ct=0;
				int i;
        // Assume that all numbers are primes, until proven otherwise.
        for(i = 0; i <= maxhalf/8+1; i++)
        {
					isprime[i] = 255;
        //	ct++;
        }

        // However, we know that 0 and 1 are not primes.  Make a note of it.
        //isprime[0] = 0; //1
        //setisp(0,0);
		isprime[0]&=~(0x1) ; //
				//isprime[1] = 1;  //3
				//setisp(1,1);
				//isprime[0]|=(0x2) ;
        // To compute all primes less than max, we need to rule out
        // multiples of all integers less than the square root of max.
        int n = (int) ceil(sqrt(max));  // See java.lang.Math class

        // Now, for each integer i from 0 to n:
        //   If i is a prime, then none of its multiples are primes,
        //   so indicate this in the array.  If i is not a prime, then
        //   its multiples have already been ruled out by one of the
        //   prime factors of i, so we can skip this case.

			char _3times=0;
			i=(max-1)/2;
			for(int j = 4; j <=i ; j +=3) //set all 3's times
        	{
               isprime[(j)>>3]&=~(0x1<<((j)&0x7));
		    }
			char i1=0;
 			int m= (n-1)/2;
			int k=(max-1)/2;
			for( i = 2; i <= m; i++)
			{
			   if(++i1==3) //skip when i is 3's times
			   {
			     i1=0;
			     continue;
			   }
			  if(getisp(i))
			  {
				_3times=((i<<2)+1)%3;  //(2*(2*i+1)%3-1)

			    for(int j = i*(2*i+2); j <= k; j = j +i +i+1)
			 	{
 			    	 if(++_3times==3) //skip when j is 3's times
					 {
					   // printf("skip i=%d,j=%d%,%d\n",2*i+1,2*j+1,_3times);
					   _3times=0;
					   continue;
    				 }
   				  if(getisp(j)) //good idea
				    isprime[(j)>>3]&=~(0x1<<((j)&0x7));
					//else

                  //ct++;
                }
			  }
            }
			/*
			 for( i = 5; i <= n; i+=2)
			 {
			   if(++i1==3) //skip when i is 3's times
			   {
			     i1=0;
			     continue;
			   }
			   int m=(i-1)/2;

               if (getisp(m))      // If i is a prime,
			   {
				_3times=(i+i)%3-1; //(nod * nod )%3 all ==1
				 for(int j = i*i; j <= max; j = j +i +i) // loop through multiples,
        		 {
 			    	 if(++_3times==3) //skip when j is 3's times
					 {
					   // printf("skip i=%d,j=%d%,%d\n",i,j,_3times);
					   _3times=0;
					   continue;
    				 }
                  int k=(j-1)/2;// they are not prime.
				   if(getisp(k)) //good idea
				   {
                     isprime[(k)>>3]&=~(0x1<<((k)&0x7)); // they are not prime.
				   }
				   else
				   {
					 //printf("cat i=%d,j=%d%,%d\n",i,j,_3times);
				     ct++;
				   }
				 }
			   }
			 }
			 */
			 /*
			 for( i = 3; i <= n; i+=2)
			 {
			   int m=(i-1)/2;
               if (getisp(m))      // If i is a prime,
			   {
                 for(int j = i*i; j <= max; j = j +i +i) // loop through multiples,
        		 {
                   int k=(j-1)/2;// they are not prime.
				   if(getisp(k)) //good idea
                   isprime[(k)/8]&=~(0x1<<((k)%8)); // they are not prime.
				   //ct++;
				 }
			   }
			 }
			 */
			/*
 			int m= (n-1)/2;
			int k=(max-1)/2;
			for( i = 1; i <= m; i++)
			{
		      //ct++;
			  if(getisp(i))
			  {
			    for(int j = i*(2*i+2); j <= k; j = j +i +i+1)
			 	{
				  if(getisp(j)) //good idea
				    isprime[(j)>>3]&=~(0x1<<((j)&0x7));
					//else

                  //ct++;
                }
			  }
            }
			*/
			/*
			int k=(max-1)/2;
		    for(int u=0;u<=k;u++)
			{
				printf("%d:%d\n",u*2+1,getisp(u));
			}
			*/





        // Now go look for the largest prime:
        int largest=2;
		  if(max <=2)
        {
        	largest=2;
        }
        else if((max%2==1)&&(getisp((max-1)/2)))
        {
      	 	largest=max;
        }
        else
        {
          	for(largest = max-1-(max %2); ; largest-=2)
        	{
        	//	ct++;  // empty loop body
			  int k=(largest-1)/2;
			  if(getisp(k))
				 break;
        	}
      	}

        // Output the result
		free(isprime);
			printf("The largest prime less than or equal to %d is %d, cycle time:%d\n" ,max, largest,ct);
			return 1;
    }