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


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


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

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

    ln x = SPLIT( n );

    printFactor( x );

    x = n/x;
    if( x == 1 ) 
    { 
        cout << " why try to split a prime number? "<< endl;
        return ;
    }

    printFactor( x );

    return ;
}


ln
getN( void )
{
    ln n;
        
    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); 
        if( m == n ) 
        {
            cout << "it appears this thing is a perfect power" << endl;
            cout << "I don't do those! (too easy)" << endl << endl;
            exit( 0 );
        }
    }
}


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