package carmichael;

import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

/**
 *
 * @author andy and tess
 */
public class Carmichael {

    /**
     * @param args the command line arguments
     */
    static boolean[] primes = new boolean[65001];//global array for our sieve

    /**
     *
     * @param args
     * @throws FileNotFoundException
     * @throws IOException
     */
    public static void main(String[] args) throws FileNotFoundException, IOException {
        Scanner in = new Scanner(new File("carmichael.in"));
        File outFile = new File("carmichael.out");
        if (!outFile.exists()) {
            outFile.createNewFile();
        }
        eratosthenes();
        BufferedWriter bw = new BufferedWriter(new FileWriter(outFile.getAbsoluteFile()));
        while (in.hasNext()) {
            int num = in.nextInt();
            if (num != 0) {
                if (carmichael(num)) {
                    bw.write(num + " is a Carmichael number.\n");
                } else {
                    bw.write(num + " is normal.\n");
                }
            }
        }
        bw.close();
    }

    private static boolean carmichael(int num) {
        if (isPrime(num)) {
            return false;
        }
        BigInteger numbi = BigInteger.valueOf(num);
        for (int i = 2; i < num; i++) {

            BigInteger modpow = BigInteger.valueOf(i).modPow(numbi, numbi);
            if (i == modpow.intValue()) {
            } else {
                return false;
            }
        }
        return true;
    }

    private static void eratosthenes() {//build a sieve of eratosthenes
        Arrays.fill(primes, true);
        primes[0] = primes[1] = false;
        for (int i = 2; i < primes.length; i++) {
            if (primes[i]) {
                for (int j = 2; i * j < primes.length; j++) {
                    primes[i * j] = false;
                }
            }
        }
    }

    private static boolean isPrime(int n) {
        return primes[n];
    }
}