import java.math.BigInteger;
import java.util.Scanner;
import java.util.concurrent.ThreadLocalRandom;

public class Console {
    public static void main(String[] args) {
        System.out.println("Please choose one of available generators.");
        System.out.println("1) Java Generator");
        System.out.println("2) ANSI-C Generator");
        System.out.println("3) GNU Generator");
        System.out.println("4) Borland Generator");
        System.out.println("5) SIMULA Generator");

        Scanner scanner = new Scanner(System.in);
        int option = scanner.nextInt();

        long seed = System.currentTimeMillis() / 1000;

        RandomNumberGenerator randomNumberGenerator;
        switch (option) {
            case 2:
                randomNumberGenerator = new ANSIC(seed);
                break;
            case 3:
                randomNumberGenerator = new GNU(seed);
                break;
            case 4:
                randomNumberGenerator = new Borland(seed);
                break;
            case 5:
                randomNumberGenerator = new SIMULA(seed);
                break;
            default:
                randomNumberGenerator = new JavaRandomNumberGeneratorWrapper();
        }

        MillerRabin millerRabin = new MillerRabin(randomNumberGenerator);

        System.out.println("Enter numbers (one by one): ");
        while ((option = scanner.nextInt()) != 0) {
            System.out.println(option);
            boolean result = millerRabin.testIsPrime(option, 100);
            System.out.println(result ? "Probably Prime" : "Complex");
        }
    }
}

class MillerRabin {

    private static long powerModulo(long a, long b, long m) {
        long n = 1;
        long x = a % m;

        for (long i = 1; i <= b; i <<= 1) {
            x %= m;
            if ((b & i) != 0) {
                n *= x;
                n %= m;
            }
            x *= x;
        }

        return n;
    }

    private RandomNumberGenerator randomNumberGenerator;

    public MillerRabin(RandomNumberGenerator randomNumberGenerator) {
        this.randomNumberGenerator = randomNumberGenerator;
    }

    public boolean testIsPrime(long n, long k) {
        if (n <= 1)
            throw new IllegalArgumentException("n > 1");
        if (n == 2)
            return true;
        if (n % 2 == 0)
            return false;

        long d = n - 1;
        int s = 0;
        while ((d % 2) == 0) {
            s++;
            d = d / 2;
        }

        outer:
        for (long i = 0; i < k; i++) {
            long a = randomNumberGenerator.nextRandom(2, n - 1);

            long x = powerModulo(a, d, n);
            if (x == 1 || x == n - 1) {
                continue;
            }

            for (int r = 1; r <= s - 1; r++) {
                x = powerModulo(x, 2, n);

                if (x == 1) {
                    return false;
                }
                if (x == n - 1) {
                    continue outer;
                }
            }

            return false;
        }

        return true;
    }
}

interface RandomNumberGenerator {
    long nextRandom(long l, long k);
}

abstract class LCG implements RandomNumberGenerator {

    private long a;
    private long xn;
    private long c;
    private long m;

    public LCG(long a, long xn, long c, long m) {
        if (!(0 < a && a < m
                && 0 <= c && c < m
                && 0 <= xn && xn < m)) {
            throw new IllegalArgumentException("Wrong arguments values");
        }

        this.a = a;
        this.xn = xn;
        this.c = c;
        this.m = m;
    }

    public long nextRandom(long l, long k) {
        if (l > k) {
            throw new IllegalArgumentException("l should be lower than k");
        }
        if (k == l) {
            return k;
        }

        BigInteger a = BigInteger.valueOf(this.a);
        BigInteger xn = BigInteger.valueOf(this.xn);
        BigInteger c = BigInteger.valueOf(this.c);
        BigInteger m = BigInteger.valueOf(this.m);

        // ((a * xn) + c) % m;
        long base = a.multiply(xn).add(c).mod(m).longValue();
        this.xn = base;

        return (base % (k - l)) + l;
    }
}

class ANSIC extends LCG {
    public ANSIC(long xn) {
        super(30517578125L, xn, 0, 34359738368L);
    }
}

class Borland extends LCG {
    public Borland(long xn) {
        super(22695477, xn, 1, 4294967296L);
    }
}

class GNU extends LCG {
    public GNU(long xn) {
        super(1103515245, xn, 12345, 4294967296L);
    }
}

class SIMULA extends LCG {
    public SIMULA(long xn) {
        super(30517578125L, xn, 0, 34359738368L);
    }
}

class JavaRandomNumberGeneratorWrapper implements RandomNumberGenerator {
    @Override
    public long nextRandom(long l, long k) {
        return (ThreadLocalRandom.current().nextLong(l, k + 1));
    }
}