code for finding all prime factors of a number using stacks
This assignment is working with stacks.
The problem posed:
Write a program that uses a stack to print the prime factors of a positive integer in decending order.
My algorithm is:
1. ask for a number
2. push 1 into the stack
3. from divisor = 2 through divisor = number
if number % divisor == 0 && divisor is prime
push divisor into stack
4. if the top item in the stack is 1
print number and stack
otherwise print stack until stack is empty
4. ask for another number or quit
The code I have so far works except for 3. finding the 'prime' factors. But, I am getting some numbers that aren't prime with my for loop condition and can't figure out a way to get all cases. Is there something very simple that I am missing here? For example 50 gives me 25 as a prime.
Code:
#include <iostream>
#include <stack>
using namespace std;
void displayBanner();
void displayQuestion();
int main()
{
int number,
halfNumber;
char userResponse;
stack<int> smallPrimeFac;
displayBanner();
displayQuestion();
cin >> userResponse;
while (userResponse == 'Y' || userResponse == 'y')
{
cout << "Enter the number: ";
cin >> number;
cout << endl;
cout << "\nThe prime factors of " << number << " are: ";
smallPrimeFac.push(1);
if((number % 2) == 0)
smallPrimeFac.push(2);
for (int i = 3; i < number - 1; i++)
{
if((number % i) == 0 && i % 2 != 0 )
smallPrimeFac.push(i);
}//end for
if (smallPrimeFac.size() == 1)
cout << number << " ";
while (!smallPrimeFac.empty())
{
cout << smallPrimeFac.top() << " ";
smallPrimeFac.pop();
}//end print stack while
cout << endl;
displayQuestion();
cin >> userResponse;
}//end while
return 0;
}//end main
void displayBanner()
{
cout << "\nThis program requests you to input a non-negative number."
<< "\nIt then calculates all the prime factors of the number,"
<< "\nand prints the factors out in decending order" << endl;
}
void displayQuestion()
{
cout << "\nWould you like to enter a number to find it's prime factors?"
<< "\n\ 'Y' to continue, anything else to quit: ";
}
As always, your help is most appreciated.
