原Java程序 Sieve.java
2006-02-18 13:24:01
/*
* 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;
/**
* 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 Sieve {
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.
boolean[] isprime = new boolean[max+1];
// Assume that all numbers are primes, until proven otherwise.
for(int i = 0; i <= max; i++) isprime[i] = true;
// However, we know that 0 and 1 are not primes. Make a note of it.
isprime[0] = isprime[1] = false;
// 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 = 0; i <= n; i++) {
if (isprime[i]) // If i is a prime,
for(int j = 2*i; j <= max; j = j + i) // loop through multiples
isprime[j] = false; // they are not prime.
}
// Now go look for the largest prime:
int largest;
for(largest = max; !isprime[largest]; largest--) ; // empty loop body
// Output the result
System.out.println("The largest prime less than or equal to " + max +
" is " + largest);
}
}
SieveLT2.java
2006-02-18 13:26:16
/*
* 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;
/**
* 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 SieveLT2 {
public static void main(String[] args) {
int tm=(int)new java.util.Date().getTime();
// 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]) //3y·¨??á?2????y // 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++;
}
}
for(int i = 0; i <= maxhalf; i++)
{
// System.out.println(i*2+1+":"+ isprime[i]);
}
// Now go look for the largest prime:
int largest=2;
if(max <=2)
{
largest=2;
}
else if((max%2==1)&&(isprime[(max-1)/2]))
{
// System.out.println("largest=max");
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);
System.out.println((int)new java.util.Date().getTime()-tm);
}
}
SIEVE7.C
2006-02-18 13:28:49
#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/3+2); //only save odd
int ct=0;
int i;
// Assume that all numbers are primes, until proven otherwise.
for(i = 0; i <= maxhalf/8*2/3+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;
char i1=0;
/* for(int j = 4; j <=i ; j +=3) //set all 3's times
{
isprime[(j)>>3]&=~(0x1<<((j)&0x7));
}
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++;
}
}
}
*/
int Flag=1;
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.
int k= (j+1)/2*6+Flag;
Flag=-Flag;
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)
for(i=maxhalf/8*2/3;i>=0;i--)
{
// ct++; // empty loop body
// int k=(largest-1)/2;
int k= (i)/2*6+Flag;
Flag=-Flag;
if(getisp(k))
{
largest=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;
}