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.

Thanks, but that didn't change much.
The problem is:
In my 'if' statement, if I include 3 on my condition as I have, then for 9, I only get 9 and 1, where I should also get 3. So I could spearate out 3 as I have 2 and start at 4. But, with 50 I will still get 25. So if I separate out each condition: 2, 3, 5, 7, 9 and make them separate cases, will that handle 99% of the prime number issues or ??? I just don't know.

Yeah, my post was worthless, so I deleted it. Let me give it some more thought and come back in a bit.

Thanks I would appreciate another brain thinking on the issue!

I searched the net to see if there was something out there before I posted, and all I found were mathematical algorithms, not the functioning kind for a programming assignment.

I appreciate the help!

Even when I do this:

Code:

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);
		if((number % 3) == 0)
			smallPrimeFac.push(3);
		if((number % 5) == 0)
			smallPrimeFac.push(5);
		if((number % 7) == 0)
			smallPrimeFac.push(7);
		if((number % 11) == 0)
			smallPrimeFac.push(11);
		for (int i =12; i < number - 1; i++)
		{
			if(number % i == 0 && i % 2 != 0)
				smallPrimeFac.push(i);
		}//end for

separating out 1, 2, 3, 5, 7, and 11 as special cases, I still have 25 as a prime number for 50 because of the loop!

This is what I had for a prgram that I needed to write for my C class. But, all it had to do is return a true or false for is the number prime. Can't figure out a translation to actually ge the numbers. But, I just found this and haven't worked on it a long time.

Code:

#include "primes.h"

int is_prime(int n)
{
	int k, limit;
	if (n == 2)
		return 1;
	if (n % 2 == 0)
		return 0;
	limit = n / 2;
	for (k = 3; k <= limit; k += 2)
		if (n % k == 0)
			return 0;
	return 1;
}

That was it!!!
Incrementing the iterator i by 2 starting at 3, that way you hit all the odd numbers. 50 no longer returns 25 and 9 returns 3.
I think I go it, my dear Watson!

Well, not really, This loop catches every prime but prints out prducts of two prime numbers as well, which isn't right!

Thanks!

Sorry, I've been preoccupied with other items. You're on the right track with a is_prime() function. Once, you complete that, the rest of it should work, at least with minimal effort.

BTW, see? I told you stacks were easy.

Adjusting the is_prime() function I have, did work for the most part, but not completely. It calculates the primes factors, but it identified some factors as primes which are not. Such as factors that are multiples of two prime factors themselves. I can't figure out how to eliminate that case. But, if nothing comes before I submit the assignment, then I will just go with it. I think that I have completed the assignment in the spirit it was intended.

Yea! You were right. The stack use part of the three assignments I had to do for this chapter were easy. It is what I have to do to use the stack that has caused me the most grief.

I still have one more to finish. But, for the life of me, couldn't figure out what I was to do. Now that I have slept on it (you were right about the sleeping too) I think I can get that one knocked out too.

Next chapter - Queues!

Thanks again for the input, if you have ideas about the prime fators that also have prime factors post it here. I will keep checking this thread for any ideas.

Hmm, I just ran your is_prime() function through a run from 0 to 99, and came up with this list of prime numbers:

Code:

1
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

As far as I can tell, it's actually correct. Are you sure you don't have an error somewhere else in your program?

Yea! for the smaller numbers it works, but if you use 456, you get back 57, 19, 3, 2, 1. If you use 2093, you get back 299, 161, 91, 23, 13, 7, and 1. These factors aren't ALL prime!
But...have I completed the assignment??? I don't know.

This is my 'completed' program to this point, anyway:

Code:

#include <iostream>
#include <stack>
using namespace std;

void displayBanner();
void displayQuestion();

int main()
{
	int number,
		limit;
	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 &#37; 2) == 0)
			smallPrimeFac.push(2);
		limit = number / 2;
		for (int i =3; i < limit; i += 2)
		{
			if(number % i == 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:  ";
}

You need to put a number on the stack if two things are true: (1) it's a factor and (2) it's prime. So your check on when to add a number to the stack should have two parts to it....

So are you saying I should include another loop for 'i' similar to the one I have for 'number' nested inside the first?

No that must not be what you are saying. I just tried that and all it did was reprint the same factors, but twice instead of just one time.

Currently, you add to the stack

Code:

if(number % i == 0)

You need another condition inside your if statement:

Code:

if ((number % i == 0) && (isprime(i))

so that the numbers that aren't prime don't get added to the stack. (You had a working isprime() posted upthread, somewhere -- you can either #include it, or just copy and paste it in.)

That is what I thought I used in the last post of my working? code:

Code:

smallPrimeFac.push(1);                 // inserting 1 in the stack first
if((number % 2) == 0)                   // 2 as a special case
smallPrimeFac.push(2);
limit = number / 2;                    // starting with 3 up to 1/2 the original number
for (int i =3; i < limit; i += 2)
{
if(number % i == 0)
              smallPrimeFac.push(i);
}//end for

then after your last post I included another loop in 'i':

Code:

 smallPrimeFac.push(1);                 // inserting 1 in the stack first
if((number % 2) == 0)                    // 2 as a special case
	smallPrimeFac.push(2);
limit = number / 2;                          // starting with 3 up to 1/2 the original number
for (int i =3; i < limit; i += 2)
{
                 if(number % i == 0)
                 int iLimit = i / 2;               //starting the isPrime check on i
                 for (int j=3;j< limit; j += 2)
 	      if(i % j == 0)
	      smallPrimeFac.push(i);
                 }//end for
}//end for

but, that only printed the same numbers in the list but twice. (for some reason my indenting got all messed up)

Does your compiler not give you warnings about that code? Something about "empty if" or the like? The only statement that is executed when (number % i==0) is the declaration of iLimit. And notice that your loop on j goes to limit, not iLimit (probably because of the previous error). And your test is backwards (if i%j ==0, i is not prime). Et cetera.

You can probably make that loop work, if you really have to; but it's far easier to just say what you mean in your if statement. You want "if i is a prime factor of number, add i to the stack". So your if statement should check both: if ((number % i == 0) && (isprime(i)). The first part checks if i is a factor, the second part checks if i is prime. You can then put the primality checking code somewhere else out of the way, so that you can see what's going on in your main loop. As McGyver pointed out, your isprime() function works like a champ; use it!