Question

Write a program using a stack to input a number and display it as a product of its prime factors in the descending order.

Answer 1

#include <iostream>
#include <stack>
using namespace std;
bool isPrime(int n); //return true if number is prime
int main()
{
    int last = 2, num, tmp; //last remembers last prime factor
    cout << "Enter number : ";
    cin >> num;
    stack<int> pFactors;
    if (isPrime(num))
    {
        cout << "Number is prime" << endl;
    }
    else
    {
        tmp = num;
        while (tmp > 1)
        {
            if (isPrime(tmp))
            {
                pFactors.push(tmp);
                break;
            }
            for (int i = last; i <= tmp; i++)
            {
                if (isPrime(i) && (tmp % i == 0))
                {
                    last = i;
                    tmp /= i;
                    pFactors.push(i);
                    break;
                }
            }
        }
        cout << num << " = ";
        while (!pFactors.empty())
        {
            cout << pFactors.top();
            pFactors.pop();
            if (!pFactors.empty())
                cout << "*";
        }
        cout << endl;
    }
    cin.ignore();
    cin.get(); //wait for "Enter"
    return 0;
}
bool isPrime(int n)
{
    if (n == 2)
        return true;
    else if (n % 2 == 0)
        return false;
    for (int i = 3; i < n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}