package problem69;

public class Problem69 {

    static boolean[] sieve;

    public static void calculateSieve(int x) {
        sieve = new boolean[x];
        for (int i = 2; i < sieve.length; i++) {
            sieve[i] = true;
        }

        for (int i = 0; i < sieve.length; i++) {
            if (sieve[i] == true) {
                for (int j = i * 2; j < sieve.length; j += i) {
                    sieve[j] = false;
                }
            }
        }
    }

    public static int totientFunciton(int nmbr) {
        double lab = nmbr;
        for (int i = 1; i < nogrannhet; i++) {
            if (nmbr % i == 0 && sieve[i]) {
                //      System.out.println(i);
                lab = lab * (1 - (1 / (double) i));
            }
        }
        //System.out.println(lab);
        return (int) lab;
    }
    static int nogrannhet = 18;

    public static void main(String[] args) {
        long beg = System.currentTimeMillis();
        calculateSieve(nogrannhet);

        double rekord = 0;

        for (int i = 10; i < 1000000; i++) {
            if ((double) i / totientFunciton(i) > rekord) {
                rekord = (double) i / totientFunciton(i);
                System.out.println("Nytt rekord för i = " + i + " - " + rekord);
            }
        }


        long end = System.currentTimeMillis();
        System.out.println("Det tog " + (end - beg) + " ms att beräkna.");
    }
}