/**
 *  @author  Hank Dolben
 *  @version 2007 Jun  9
 *
 *  Copyright (c) 2006-2007 by Hank Dolben
 *  Licensed under the Open Software License version 3.0
 *  http://opensource.org/licenses/osl-3.0.php
 */

/**
 *  for finding the prime factors of a number
 *
 *  the number must be less than 2^63
 *
 *  will not succeed for numbers with
 *  more than one prime factor > prime[_max_count]
 *  or primes > prime[_max_count]^2
 */
public class Primes {

    private static int _max_count = 100000; /* maximum number of primes */
    private static int _count     =      0; /* number of primes         */
    private static int _prime[];            /* array of primes          */
    
    /**
     *  returns the greatest number that can be a factor of n
     */
    private static long ceiling( long n ) {
        return Math.round(Math.ceil(Math.sqrt(n)));
    }
    
    /**
     *  returns true iff n is prime
     */
    private static boolean prime( long n ) {
        long limit = ceiling(n);
        int  i;
        
        for ( i = 0; i < _count && _prime[i] <= limit; i++ ) {
            if ( n%_prime[i] == 0 ) {
                return false;
            }
        }
        return true;
    }
    
    /**
     *  initializes the array of primes
     */
    private static void init( ) {
        _prime    = new int[_max_count];
        _prime[0] = 2;
        _count    = 1;
    }
    
    /**
     *  returns the next element added to the array of primes
     */
    private static int next( ) throws Exception {
        int p = _prime[_count-1];
        
        while ( true ) {
            if ( _count == _max_count ) {
                throw new Exception();
            }
            if ( prime(++p) ) {
                _prime[_count++] = p;
                return p;
            }
        }
    }
    
    /**
     *  returns the least prime factor of n
     *
     *  primes less than _prime[_count-1] have already been factored out
     */
    private static long factor( long n ) throws Exception {
        long limit = ceiling(n);
        int  p     = _prime[_count-1];
        
        while ( n%p != 0 ) {
            if ( p > limit ) {
                return n;
            }
            p = next();
        }
        return p;
    }
    
    /**
     *  prints the prime factors of a given number,
     *  like "2^3*5 = 40" or "41 is prime"
     */
    private static int show( long n ) {
        long    k      = n;      /* original number to factor        */
        int     m      = 0;      /* number of previous prime factors */
        long    p0     = 1;      /* previous prime factor            */
        long    p1;              /* current prime factor             */
        boolean failed = false;  /* failed to find all prime factors */
        
        do {
            try {
                p1 = factor(n);
            } catch ( Exception e ) {
                p1 = n;
                failed = true;
            }
            n /= p1;
            if ( p1 != p0 ) {
                if ( m > 1 ) {
                    System.out.print("^"+m);
                }
                if ( m > 0 ) {
                    System.out.print('*');
                }
                if ( failed ) {
                    System.out.print("...\n");
                }
                System.out.print(p1);
                m = 0;
                p0 = p1;
            }
            m += 1;
        } while ( n != 1 );
        if ( m > 1 ) {
            System.out.print("^"+m);
        }
        if ( failed ) {
            System.out.println(
                " is not factored, because either\n"+
                " it has factors greater than "+
                _prime[_count-1]+" (prime #"+_count+")\n"+
                "  or is a prime greater than "+_prime[_count-1]+"^2");
            return 1;
        } else if ( p1 == k ) {
            System.out.println(" is prime");
        } else {
            System.out.println(" = "+k);
        }
        return 0;
    }
    
    /**
     *  prints the prime factors of a given number that is small enough
     *  or another message when misused
     */
    public static void main( String argv[] ) throws Exception {
        int result = 1;
        
        try {
            int  i;
            long n = 0; /* number to factor */
            
            if ( argv.length > 3 ) {
                throw new Exception();
            }
            for ( i = 0; i < argv.length; i++ ) {
                if ( argv[i].equals("-m") ) {
                    _max_count = Integer.parseInt(argv[++i]);
                } else {
                    if ( n != 0 ) {
                        throw new Exception();
                    }
                    n = Long.parseLong(argv[i]);
                    if ( n < 2 ) {
                        System.out.println(n+" < "+2);
                        System.exit(1);
                    }
                }
            }
            if ( n == 0 ) {
                throw new Exception();
            }
            init();
            result = show(n);
        } catch ( Exception e ) {
            System.out.println("Usage: java Primes (number to factor)"+
                " [-m (maximum number of primes)]");
            System.out.println("       where 1 < (number to factor) < 2^63");
        }
        System.exit(result);
    }
    
}