// Sieve.java -- version 2.0
// Andrew Schulman, August 1997
// andrew@ora.com; http://www.sonic.net/~undoc
// for Web Review article "Scripting Java"

// CLASSPATH=.;C:\Program Files\Netscape4\Communicator\Program\Java\classes\java40.jar -- what happens in MSIE???
import netscape.javascript.JSObject;

import java.applet.*;

public class Sieve extends Applet implements Runnable {
    private Thread thr = null;
    private boolean map[];
    private int top;
    private String str = "";
    private boolean done = false;
    private int size;

    public long getMax()            { return ((long) size*size) - 1; }
    
    // skip multiples of 2, 3 (1/2 * 2/3 = 2/6 = 1/3)
    private static int N(int x)     { return (x / 3); }

    // estimate number of primes, using Legendre formula (1778)
    public double legendre(long x) {
        return Math.floor(x / (Math.log(x) - 1.08366));
        }

    // internal: assumes 2,3 already handled
    private boolean _isPrime(long x) throws Exception {
        if (done == false)
            throw new Exception("not done");

        if (x < top)    // problem here???!!! getting multiples of 5 back?!?!?
            return (map[N((int) x)] == false); // in map, prime = false !
        else
            return (_smallestFactor(x) == 1);
        }

    public boolean isPrime(long x) throws Exception {
        if (x < 2)
            return false;   // 1, 0, negative numbers
        if ((x == 2) || (x == 3))
            return true;
        if (((x % 2) == 0) || ((x % 3) == 0))
            return false;
        return _isPrime(x);
        }

    public long nextPrime(long x) throws Exception {
        if (x < 2) return 2;
        
        if ((x % 2) == 0) x++;
        else x+=2;

        while (! isPrime(x))
            x += 2;             // optimize later to use _isPrime
        
        return x;
        }

    public long numPrimes(long start, long stop) throws Exception {
        long count = 0;
        if (stop < start) {
            long temp = start;
            start = stop;
            stop = temp;
            }

        if (stop < 2) return 0;
        if (stop < 3) return 1;
        if (stop < 5) return 2;
        
        if (start <= 2) count = 1;
        else if (start <= 3) count = 2;

        // move off multiples of 2,3
        while (((start % 2) == 0) || ((start % 3) == 0))
            start++;
        while (((stop % 2) == 0) || ((stop % 3) == 0))
            stop--;
        
        if (stop < size) {
            int i, strt=N((int)start), stp=N((int)stop);
            for (i=strt; i<=stp; i++)
                if (! map[i])
                    count++;
            }
        else {
            // to do: if partially within range, pick up from faster loop
            long i;
            int incr2 = (((start/3)%2)==0) ? 2 : 4;
            for (i=start; i<=stop; i+=(incr2=6-incr2))
                if (_isPrime(i))
                    count++;
            }
        
        return count;
    }

    // internal version: assumes 2,3 have already been checked
    private int _smallestFactor(long x) throws Exception {
        long sqrtx = (long) Math.sqrt(x);
        if (sqrtx > (long) size) // *not* top!!
            throw new Exception("smallestFactor: too big");

        int i, n, incr, sqtx=(int)sqrtx;
        // need to yield in here every now and then so user can cancel?
        for (i=5, incr=4, n=1; i<=sqtx; i+=(incr=6-incr), n++)
            if (! map[n])
                if ((x % (long) i) == 0)
                    return i;

        // still here: it's prime
        return 1;
        }
        
    public int smallestFactor(long x) throws Exception {
        if ((x % 2) == 0) return 2;
        if ((x % 3) == 0) return 3;
        return _smallestFactor(x);
        }

    public String getInfo() {
        return ("size: " + String.valueOf(size) + "\n" +
                "top: " + String.valueOf(top) + "\n" +
                "map_size: " + String.valueOf(N(size)+1) + "\n" +
                "max: " + String.valueOf(getMax()) + "\n");
        }

    public void start() {
        if (thr == null)
            (thr = new Thread(this)).start();
        }

    public void stop() {
        if (thr != null) {
            thr.stop();
            thr = null;
            }
        }

	public void sieve(int sieve_size) {
        int i, map_size, sqrt_size, n, incr;
        int nn, ii, incr2;

		if (done) return;

		if (sieve_size != 0)
			size = sieve_size;

        this.showStatus("Sieve starting; size=" + String.valueOf(size));
        
        top = N(size) + (size % 2);
        map_size = N(size) + 1;
        map = new boolean[map_size];

        // this takes some time; really necessary?
        for (i=0; i<map_size; i++) map[i] = false;

        sqrt_size = (int) Math.sqrt(size);
        for (i=5, incr=4, n=1; i<=sqrt_size; i+=(incr=6-incr), n++)
            if (! map[n])                    // found a prime
            {
                nn = N(i * i);
                ii = 2 * i;
                incr2 = ii - (N(i*(i+(6-incr))) - nn);
                
                // all multiples are composites
                for (; nn < top; nn += (incr2=ii-incr2))
                    map[nn] = true;  // true = composite; false = prime!
            }

        done = true;
        this.showStatus("Sieve done");
		
		// try to fix "document.PrimeEngine has no properties" problem
		// by having Java applet set a JavaScript variable on page
		JSObject jsroot = JSObject.getWindow(this);
		jsroot.eval("self.ready = 1;");
		jsroot.eval("alert('Sieve is ready!');");
		
        }

	public void sieve() { sieve(0); }	// use pre-establed size

    public void run() {
        int i, map_size, sqrt_size, n, incr;
        int nn, ii, incr2;

		// try to fix "document.PrimeEngine has no properties" problem
		// by having Java applet set a JavaScript variable on page
		JSObject jsroot = JSObject.getWindow(this);
		jsroot.eval("self.loaded = 1;");
		jsroot.eval("alert('Java applet is loaded!');");
		
        if (done) return;

        // size can be set in <PARAM NAME=size VALUE=x> tag
        String size_str = getParameter("size");
        if (size_str == null)
            size = 1000000;
        else {
            try {
                size = Integer.parseInt(size_str);
                }
            catch (NumberFormatException e) {
                size = 1000000;
                }
            }
		}
    }