package math.prime;

import java.util.BitSet;

public class Primes06 {
    public static void main(String[] args) {
        int liczb = 100000000;
        //JP
        int count = 0;
        long start = System.currentTimeMillis();
        BitSet b = eratoHorstmannImproved(liczb);
        long end = System.currentTimeMillis();
        System.out.println("Sito Eratostenesa poprawioną metoda Horstmanna");
        System.out.println((end - start) + " milisekund");
        for (int k = 2; k <= liczb; k++) {
            if (b.get(k)) {
                count++;
            }
        }
        System.out.println(count + " liczb pierwszych");

        //Horstmann
        int count1 = 0;
        long start1 = System.currentTimeMillis();
        BitSet b1 = eratoHorstmann(liczb);
        long end1 = System.currentTimeMillis();
        System.out.println("Sito Eratostenesa metodą Horstmanna");
        System.out.println((end1 - start1) + " milisekund");
        for (int k = 2; k <= liczb; k++) {
            if (b1.get(k)) {
                count1++;
            }
        }
        System.out.println(count1 + " liczb pierwszych");
        //Eratostenes tradycyjny
        int count2 = 0;
        long start2 = System.currentTimeMillis();
        boolean[] b2 = eratoInternet(liczb);
        long end2 = System.currentTimeMillis();
        System.out.println("Sito Eratostenesa z Internetu");
        System.out.println((end2 - start2) + " milisekund");
        for (boolean b5 : b2) {
            if (b5) {
                count2++;
            }
        }
        System.out.println(count2 + " liczb pierwszych");
        //sito Arkina
        int count3 = 0;
        long start3 = System.currentTimeMillis();
        boolean[] b3 = eratoInternet(liczb);
        long end3 = System.currentTimeMillis();
        System.out.println("Sito Atkina z Internetu");
        System.out.println((end3 - start3) + " milisekund");
        for (boolean b4 : b3) {
            if (b4) {
                count3++;
            }
        }
        System.out.println(count3 + " liczb pierwszych");
    }

    public static BitSet eratoHorstmannImproved(int n) {
        BitSet b = new BitSet(n + 1);
        b.set(2, n + 1);

        int i = 2;
        while (i * i <= n) {
            int k = 2 * i;
            while (k <= n) {
                b.clear(k);
                k += i;
            }
            i = b.nextSetBit(i + 1);
        }
        return b;
    }
    //Metoda opublikowana w książce Horstmanna i Cornella 2008. Java. Posstawy. Wyd. VIII
    //Wyd. Helion, str. 753
    //W metodyzie - dla celów porównania zakomentowano linie służące do
    //obliczenia liczby liczb pierwszych. Poprawiono też typ zwracany z int na BitSet.
    //Zwracane jest b, a nie count.
    public static BitSet eratoHorstmann(int n) {
        BitSet b = new BitSet(n + 1);
        //int count = 0;
        int i;
        for (i = 2; i <= n; i++) {
            b.set(i);
        }
        i = 2;
        while (i * i <= n) {
            if (b.get(i)) {
                //count++;
                int k = 2 * i;
                while (k <= n) {
                    b.clear(k);
                    k += i;
                }
            }
            i++;
        }
        /*
         while (i <= n) {
         if (b.get(i)) {
         //count++;
         }
         i++;
         }
         */
        return b;
    }
    //Metoda znaleziona w Internecie
    public static boolean[] eratoInternet(int max) {
        int pol = (max + 1) >> 1;
        boolean[] wynik = new boolean[max + 1];
        for (int i = 2; i <= max; ++i) {
            wynik[i] = true;
        }
        int p = 2;
        while (p < pol) {
            for (int z = p << 1; z <= max; z += p) {
                wynik[z] = false;
            }
            while ((++p < pol) && (!wynik[p])) ;
        }
        return wynik;
    }
    //Metoda znaleziona w Internecie
    public static boolean[] atkinInternet(int max) {
        boolean[] primes = new boolean[max + 1];
        primes[2] = true;
        primes[3] = true;
        int root = (int) Math.ceil(Math.sqrt(max));
        for (int x = 1; x < root; x++) {
            for (int y = 1; y < root; y++) {
                int n = 4 * x * x + y * y;
                if (n <= max && (n % 12 == 1 || n % 12 == 5))
                    primes[n] = !primes[n];
                n = 3 * x * x + y * y;
                if (n <= max && n % 12 == 7)
                    primes[n] = !primes[n];
                n = 3 * x * x - y * y;
                if ((x > y) && (n <= max) && (n % 12 == 11))
                    primes[n] = !primes[n];
            }
        }
        for (int i = 5; i <= root; i++)
            if (primes[i])
                for (int j = i * i; j < max; j += i * i)
                    primes[j] = false;
        return primes;
    }
}
