// ----------------------------------------------------------------------
// 
//  Module:          rho.cc
//  Description:     Factor an integer using Pollard's Rho algorithm.
//  Contributed by:  Rene Peralta and Sean Fenton
//  Date:            2002
//  
// ----------------------------------------------------------------------
#include <lnv3/lnv3.h>
#include <nttl/isPrime.h> 
#include <nttl/gcd.h> 


void
main_loop( void );
ln getN( void );
ln SPLIT( ln &n );
void printFactor( ln &f );
void factor( ln n);


int 
main()
{
    while (1) main_loop();
}

void
main_loop( )
{
    ln n = getN( );
    factor(n);
}

void factor( ln n )
{
    while (n % 2 == 0) { cout << " 2 " ; n = n/2; }
    while (n % 3 == 0) { cout << " 3 " ; n = n/3; }
    while (n % 5 == 0) { cout << " 5 " ; n = n/5; }
    while (n % 7 == 0) { cout << " 7 " ; n = n/7; }
    
    if (n == 1) return;
    ln x = SPLIT( n );

    if (IsPrime(x)) 
      { 
	cout << x << " " ; 
	factor(n/x);
      }
    else { factor(x); factor(n/x);}
}


ln
getN( void )
{
    ln n;
        
    cout << endl;
    cout << endl;
    cout << "input a positive integer (0 to exit)" << endl;
    cin >> n ;
    cout << endl << endl;
 
    if (n == 0) 
    {
        cout << "bye " << endl;
        exit( 0 );
    }
        
    if( n.IsNegative( ) )
    { 
        cout << -1 << endl;
        n = -n;
    }

    return n;
}


ln SPLIT( ln &n )
{
    if (n <= 0) exit(0);
    if (n == 1) return(1);
        
    if (IsPrime(n)) return(n);

    ln x = ln( ).Random(20) % n;
    ln y = x;
        
    ln m;
    long i = 0;

    while (1)
    {
        //
        // Uncomment the following if you want to see a running
        // count of the number of GCD's performed.
        // 
        // cout << i++ << "\n";
        y = ( y*y + 1 ) % n;
        x = ( x*x + 1 ) % n;
        x = ( x*x + 1 ) % n;
        m = GCD( x-y, n );
        if( ( m > 1 ) && ( m < n ) )
            return(m); 
    }
}


void
printFactor( ln& f )
{
    cout << f ;
    if( IsPrime( f ) )
        cout << "  prime"<< endl;
    else
        cout << "  composite" << endl;
}