#include <iostream>

// This program finds the prime factorization of an
// integer 'n' entered by the user.
//
// For example,
//
//     60 = 2 * 2 * 3 * 5.
//
// Exercises:
//
// 1. Modify the program so that the user must enter
//    an integer greater than or equal to 2. If the
//    user enters a smaller value, repeatedly query
//    the user until an acceptable value is entered.
//
// 2. Currently, if this program is asked to factor
//    the integer 1714739208, the output is
//
//        2, 2, 2, 3, 7, 13, 19, 31, 31, 43,
//
//    Notice the trailing comma. This is rather
//    unsatisfying.
//
//    You can fix this in at least two ways:
//
//    A. If a factor is the first factor being printed,
//       print only that factor. Otherwise, first print
//       a comma and a space, followed by the factor.
//
//    B. If 'possible_factor == n', then this is the
//       final factor. Print it without a trailing
//       comma and space.
//
//    Solution B is probably easier to implement here.
//    However, it is not always possible to know in
//    advance when the final item in a sequence is
//    being printed.
//
//    How would you implement Solution A?
//
// 3. Suppose you instead wanted the factorization of
//    1714739208 to be printed as
//
//        2^3 * 3 * 7 * 13 * 19 * 31^2 * 43
//
//    Modify the program so that repeated factors are
//    represented using exponents. Do not print "^1"
//    when a factor occurs only once.

// Function declarations
int main();

// Function definitions
int main() {
    int n{};

    std::cout << "Enter a positive integer to be factored: ";
    std::cin  >> n;

    int possible_factor{ 2 };

    while ( n > 1 ) {
        while ( n%possible_factor == 0 ) {
            std::cout << possible_factor << ", ";
            n /= possible_factor;
        }

        // Ideally, we could proceed directly to the
        // next prime number. However, simply testing
        // each successive integer works as well.
        //
        // Why will a composite value of
        // 'possible_factor' never actually be printed?
        ++possible_factor;
    }

    // Print an end-of-line after all factors have
    // been printed.
    std::cout << std::endl;

    return 0;
}



























// Hint for Exercise 1:
//
// Use a loop that repeatedly queries the user and
// terminates only when
//
//     n >= 2.



























// Hint for Exercise 2, Solution A:
//
// You need to remember whether a factor has already
// been printed.
//
// What type of variable could store either
//
//     true
//
// or
//
//     false?
//
// Initially, no factor has been printed. After the
// first factor is printed, update this variable.
//
// Before printing each subsequent factor, use its
// value to decide whether ", " should first be
// printed.



























// Here is one solution to Exercises 1 and 2 using
// Solution A:
/*
int main() {
    int n{};

    while ( true ) {
        std::cout << "Enter an integer greater than "
                  << "or equal to 2: ";
        std::cin  >> n;

        if ( n >= 2 ) {
            break;
        }
    }

    int possible_factor{ 2 };
    bool first_factor{ true };

    while ( n > 1 ) {
        while ( n%possible_factor == 0 ) {
            if ( first_factor ) {
                first_factor = false;
            } else {
                std::cout << ", ";
            }

            std::cout << possible_factor;
            n /= possible_factor;
        }

        ++possible_factor;
    }

    std::cout << std::endl;

    return 0;
}
*/

























// Here is one solution to Exercises 1 and 2 using
// Solution B:
/*
int main() {
    int n{};

    while ( true ) {
        std::cout << "Enter an integer greater than "
                  << "or equal to 2: ";
        std::cin  >> n;

        if ( n >= 2 ) {
            break;
        }
    }

    int possible_factor{ 2 };

    while ( n > 1 ) {
        while ( n%possible_factor == 0 ) {
            std::cout << possible_factor;

            if ( possible_factor != n ) {
                std::cout << ", ";
            }

            n /= possible_factor;
        }

        ++possible_factor;
    }

    std::cout << std::endl;

    return 0;
}
*/

























// Hint for Exercise 3:
//
// Instead of immediately printing a factor each
// time it divides 'n', count how many times that
// factor divides 'n'.
//
// For each possible factor:
//
//     1. Start a counter at 0.
//
//     2. Each time 'possible_factor' divides 'n',
//        divide 'n' by that factor and increment
//        the counter.
//
//     3. If the counter is greater than 0, print
//        the factor.
//
//     4. If the counter is greater than 1, also
//        print '^' followed by the counter.
//
// You will still have to avoid printing " * " after
// the final factor.



























// Here is one solution to all three exercises:
/*
int main() {
    int n{};

    while ( true ) {
        std::cout << "Enter an integer greater than "
                  << "or equal to 2: ";
        std::cin  >> n;

        if ( n >= 2 ) {
            break;
        }
    }

    int possible_factor{ 2 };
    bool first_factor{ true };

    while ( n > 1 ) {
        int exponent{ 0 };

        while ( n%possible_factor == 0 ) {
            n /= possible_factor;
            ++exponent;
        }

        if ( exponent > 0 ) {
            if ( first_factor ) {
                first_factor = false;
            } else {
                std::cout << " * ";
            }

            std::cout << possible_factor;

            if ( exponent > 1 ) {
                std::cout << "^" << exponent;
            }
        }

        ++possible_factor;
    }

    std::cout << std::endl;

    return 0;
}
*/