/*
SIEVE OF ERATOSTHENES from BYTE magazine --------------------
-- compiled with jdk 1.1.7b with optimize on ( -O)
-- Run times on 300 MHz Pentium 2 Windows 95
-- in order of output, from fresh boot
-------------------------------------------------------------
JDK 1.1.7B
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.1_03-b02)
Java HotSpot(TM) Client VM (build 1.4.1_03-b02, mixed mode)
Microsoft Jview 5.00.3805
-------------------------------------------------------------
C:\Java\Sieve>makerun Sieve 10000
adding: Sieve.class (in=1033) (out=630) (deflated 39%)
10000 iterations
1899 primes
5720 milliseconds
10000 iterations
1899 primes
15430 milliseconds
10000 iterations
1899 primes
6100 milliseconds
C:\Java\Sieve>makerun Sieve 10000
adding: Sieve.class (in=1033) (out=630) (deflated 39%)
10000 iterations
1899 primes
5330 milliseconds
10000 iterations
1899 primes
14450 milliseconds
10000 iterations
1899 primes
6100 milliseconds
-------------------------------------------------------------
C:\Java\Sieve>set classpath=
C:\Java\Sieve>gcj --version
GCJ.EXE (GCC) 3.3.1 (mingw special 20030804-1)
Copyright (C) 2003 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
C:\Java\Sieve>gcj -O3 --main=Sieve Sieve.java
C:\Java\Sieve>a 10000
10000 iterations
1899 primes
7360 milliseconds
C:\Java\Sieve>a 10000
10000 iterations
1899 primes
7580 milliseconds
-------------------------------------------------------------
maw
*/
public class Sieve {
static final int TSIZE = 8192;
public static void main(String args[]) {
int NUM = Integer.parseInt(args[0]);
byte [] flags = new byte[TSIZE + 1];
int count = 0;
System.out.print(NUM + " iterations \n");
long t1 = System.currentTimeMillis();
while (NUM-- > 0) {
count = 0;
for (int i=0; i <= TSIZE; i++) {
flags[i] = 1;
}
for (int i=0; i <= TSIZE; i++) {
if (flags[i] == 1) {
int prime = i + i + 3;
int k = i + prime;
while( k <= TSIZE) {
flags[k] = 0;
k = k + prime;
}
count++;
}
}
}
long t2 = System.currentTimeMillis();
System.out.print(count + " primes \n");
System.out.print((t2 - t1) + " milliseconds \n");
}
}