// This program factors integers entered by its user. Specifically, the main
// program consists of a loop that reads an integer from the user, factors
// it into prime factors, and then asks the user if they want to factor another
// number. This continues until the user says they don't want to do more
// factoring. Note that this program consists of a collection of static methods,
// since objects don't really contribute much to such a simple problem.

// History
//   December 2003 -- Created by Doug Baldwin, based on an original in
//     Object Pascal by Doug Baldwin.




import java.io.*;




class Factor {




    private static final int INVALID = -1;			// Indicates an invalid integer entered by the user




    // The main method contains the loop that reads integers and continuation requests
    // from the user. A subsidiary method does the actual factoring and printing of
    // factors.
        
    public static void main( String args[] ) {

        try {

            BufferedReader keyboard = new BufferedReader( new InputStreamReader( System.in ) );

            String more = "y";

            while ( more.equalsIgnoreCase("y") ) {

                int toFactor = readNumber( keyboard, "Enter a number to factor", 2, INVALID );

                System.out.print( toFactor + " = " );
                factor( toFactor );

                System.out.print( "Factor another number (y/n)? " );
                more = keyboard.readLine();
            }
        }
        catch ( IOException error ) {
            // Abort if anything goes wrong reading from the keyboard
            System.out.println( "Can't read from keyboard. Aborting..." );
        }
    }




    // factor. This method takes an integer as its parameter, and prints all of its prime
    // factors. This method uses a helper method findFactor to find a prime factor of
    // n -- findFactor will return n itself if n has no prime factors. If findFactor finds
    // a real factor, then this method prints it, a "X", and then prints the factors of
    // n divided by the factor. Otherwise, this method just prints n and returns.

    // Preconditions: n >= 2.

    private static void factor( int n ) {

        int f = findFactor( n );

        if ( f == n ) {
            System.out.println( n );
        }
        else {
            System.out.print( f + " X " );
            factor( n / f );
        }
    }




    // findFactor. This method finds a prime factor of n by brute-force searching.
    // It starts by checking to see if 2 factors n, then 3, and so forth up to
    // the square root of n (if no number up to the square root factors n, then
    // nothing will). Note that this method is guaranteed to find a prime factor,
    // since it returns the first (i.e., smallest) factor it finds. This means that
    // the returned factor can't have any factors itself, i.e., it's prime.

    private static int findFactor( int n ) {

		for ( int f = 2; f < Math.floor(Math.sqrt(n)); f++ ) {

            if ( n % f == 0 ) {
                return f;
            }
        }

        return n;				// No factor found, n must be prime
    }




    // readNumber, a method that reads a natural number from the user and
    // returns it. Parameters to this method are the reader to read from,
    // a prompt to display, the lowest acceptable number, and the highest
    // acceptable number. Either the minimum or maximum numbers may be the
    // constant INVALID, in which case the corresponding bound isn't checked.
    // This method will keep prompting and reading until it gets a number in
    // the right range. If this function is completely unable to read from the
    // keyboard, it returns the minimum acceptable value as a default.

    private static int readNumber( BufferedReader keyboard, String prompt, int min, int max ) {

        int result = INVALID;

        while ( result == INVALID ) {

            System.out.print( prompt + ": " );

            try {
                String input = keyboard.readLine();
                result = Integer.parseInt( input );
            }
            catch ( NumberFormatException error ) {
                System.out.println( "Input must be a number. Try again..." );
            }
            catch ( IOException error ) {
                System.out.println( "Error reading keyboard. Using default value." );
                result = min;
            }

            if (  min != INVALID  &&  result != INVALID  &&  result < min  ) {
                System.out.println( "Input must be at least " + min + ". Try again..." );
                result = INVALID;
            }
            if (  max != INVALID  &&  result != INVALID  &&  result > max  ) {
                System.out.println( "Input must be no more than " + max + ". Try again..." );
                result = INVALID;
            }
        }

        return result;
    }
    
}