#include <iostream>
#include <string>
#include "Map.h"

#pragma warning (disable: 4786)

using namespace std;

// Test program for Assignment #5
// You may not make any changes.


// Print items in array m.
void printFactors( const vector<int> & m )
{
    cout << m[ 0 ];
    for( int i = 1; i < m.size( ); i++ )
        cout << " " << m[ i ];
    cout << endl;
}

// Return vector containing the prime factorization of n.
// Precondition: n > 1.
vector<int> getFactors( int n )
{
    vector<int> result;

    for( int i = 2; i * i <= n; )
    {
        if( n % i == 0 )
        {
            result.push_back( i );
            n /= i;
        }
        else
            i++;
    }

    if( n > 1 )
        result.push_back( n );

    return result;
}

// Print factorizations of number in Map m that have
// at least threshold factors.
void printLargeFactorizations( Map<int,vector<int> > m, int threshold )
{
    vector<int> keys = m.getAllKeys( );
    for( int i = 0; i < keys.size( ); i++ )
    {
        int num = keys[ i ];
        if( m[ num ].size( ) >= threshold )
        {
            cout << num << ": ";
            printFactors( m[ num ] );
        }
    }
}

// Remove all primes from the map.
void removePrimes( Map<int,vector<int> > & m )
{
    vector<int> keys = m.getAllKeys( );
    for( int i = 0; i < keys.size( ); i++ )
        if( m[ keys[ i ] ].size( ) == 1 )
            m.remove( keys[ i ] );
}

// Sample main.
int main( )
{
    Map<int,vector<int> > m;
    const int n = 100;
    vector<int> factorization;

    for( int i = 2; i <= n; i++ )
    {
        factorization = getFactors( i );
        if( factorization.size( ) >= 1 )
            m[ i ] = factorization;
    }

    removePrimes( m );

    cout << "Number of nonprimes less than " << n
         << " is " << m.getSize( ) << endl;

    printLargeFactorizations( m, 4 );

    return 0;
}