sieve2.java

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

/*
 * Copyright (c) 2000 David Flanagan.  All rights reserved.
 * This code is from the book Java Examples in a Nutshell, 2nd Edition.
 * It is provided AS-IS, WITHOUT ANY WARRANTY either expressed or implied.
 * You may study, use, and modify it for any non-commercial purpose.
 * You may distribute it non-commercially as long as you retain this notice.
 * For a commercial use license, or to purchase the book (recommended),
 * visit http://www.davidflanagan.com/javaexamples2.
 */
//package com.davidflanagan.examples.basics;
//------------------------Modified By Lu Tao 20030501-----------------------
/**
 * This program computes prime numbers using the Sieve of Eratosthenes
 * algorithm: rule out multiples of all lower prime numbers, and anything
 * remaining is a prime.  It prints out the largest prime number less than
 * or equal to the supplied command-line argument.
 **/
public class Sieve2 {
    public static void main(String[] args) {
        // We will compute all primes less than the value specified on the
        // command line, or, if no argument, all primes less than 100.
        int max = 100;                           // Assign a default value
        try { max = Integer.parseInt(args[0]); } // Parse user-supplied arg
        catch (Exception e) {}                   // Silently ignore exceptions.

        // Create an array that specifies whether each number is prime or not.
        int maxhalf=(max+1)/2;
        boolean[] isprime = new boolean[maxhalf+1]; //only save odd
        int ct=0;

        // Assume that all numbers are primes, until proven otherwise.
        for(int i = 0; i <= maxhalf; i++) 
        {
        	isprime[i] = true;
        //	ct++;
        }

        // However, we know that 0 and 1 are not primes.  Make a note of it.
        isprime[0] = false; //1
				isprime[1] = true;  //3
        // 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) Math.ceil(Math.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.
     
			 for(int i = 3; i <= n; i+=2) { 
            if (isprime[(i-1)/2])        //除法指令不算慢    // If i is a prime, 
                for(int j = 3*i; j <= max; j = j +i +i) // loop through multiples,
                {
                   isprime[(j-1)/2] = false;               // they are not prime.
                //    ct++;
                }
        }
       

        // Now go look for the largest prime:
        int largest=2;
        if(max <=2)
        {
        	largest=2;
        }
        else if((max%2==1)&&(isprime[(max-1)/2]))
        {
        	largest=max;
        }
        else
        {
        	for(largest = max-1-(max %2); !isprime[(largest-1)/2]; largest-=2) 
        	{
        	//	ct++;  // empty loop body
        	}
      	}
        
        // Output the result
        System.out.println("The largest prime less than or equal to " + max +
			   " is " + largest+" cycle time:"+ct);
    }
}