Standard Sieve performance

From: Mark A. Washburn (Reply7471859353_at_wmconnect.com)
Date: 02/27/04 

Date: 26 Feb 2004 16:18:05 -0800

/*

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");
    }
}

Relevant Pages