/* ************************************************************************
 * Clase con dos funciones estáticas de aritmética
 * 
 * Rodolfo Valeiras Reina, 5 de enero de 2001.
 * ************************************************************************
 */
class TeorNum {
    /*
     * EsPrimo devuelve «true» o «false» según el argumento sea o no primo.
     * El argumento debe ser un número entero (int) mayor que uno. El mayor
     * int es 2147483647 (2^31-1).
     * 
     * Adaptado de una función en Turbo Pascal de GUY MCLOUGHLIN.
     */
    static boolean EsPrimo(int x) {
        int lo_Sqrt, lo_Loop;
        if ((x % 2) == 0) {
            return x == 2;
        }
        if ((x % 3) == 0) {
            return x == 3;
        }
        if ((x % 5) == 0) {
            return x == 5;
        }
        lo_Sqrt = (int) Math.floor(Math.sqrt(x));
        lo_Loop = 7;
        while (lo_Loop <= lo_Sqrt) {
            if ((x % lo_Loop) == 0) {
                return false;
            }
            lo_Loop += 2;
        }
        return true;
    }
    /*
     * Factores devuelve una matriz lineal con los factores primos y sus potencias
     * de un número entero (int) mayor que 1. Por ejemplo, si el argumento es 100,
     * la matriz devuelta contiene los valores {2, 2, 5, 2}.
     * 
     * Adaptado de un pequeño programa que escribí hace tiempo (en 1996) en Turbo
     * Pascal.
     */
    static int[] Factores(int x) {
        int Fact[];
        boolean L[];
        int p, r, s, i;
        Integer I;
        java.util.Vector V = new java.util.Vector();
        r = (int) Math.floor(Math.sqrt(x)) + 1;
        L = new boolean[r];
        for (i = 0; i < r; i++) {
            L[i] = true;
        }
        p = 2;
        while (p < r) {
            i = 0;
            while ((x % p) == 0) {
                i++;
                x /= p;
            };
            if (i >= 1) {
                V.addElement(new Integer(p));
                V.addElement(new Integer(i));
            };
            s = p * p;
            while (s < r) {
                L[s] = false;
                s += p;
            };
            do {
               p++;
            } while ((p < r) && ! L[p]);
        }
        if (x > 1) {
            V.addElement(new Integer(x));
            V.addElement(new Integer(1));
        }        
        Fact = new int[V.size()];
        for (i = 0; i < Fact.length; i++) {
            I = (Integer) V.elementAt(i);
            Fact[i] = I.intValue();
        }
        return Fact;
    }
}