Thread: code for finding all prime factors of a number using stacks

  1. #1
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164

    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.
    Last edited by clegs; 11-24-2007 at 11:53 PM.

  2. #2
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    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&#37; of the prime number issues or ??? I just don't know.
    Last edited by clegs; 11-25-2007 at 12:05 AM.

  3. #3
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Yeah, my post was worthless, so I deleted it. Let me give it some more thought and come back in a bit.

  4. #4
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    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!

  5. #5
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    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;
    }
    Last edited by clegs; 11-25-2007 at 12:24 AM.

  6. #6
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    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!
    Last edited by clegs; 11-25-2007 at 12:40 AM.

  7. #7
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    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.

  8. #8
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    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.
    Last edited by clegs; 11-25-2007 at 09:48 AM.

  9. #9
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    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?

  10. #10
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    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:  ";
    }
    Last edited by clegs; 11-25-2007 at 10:26 AM. Reason: Inserting code

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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....

  12. #12
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    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.
    Last edited by clegs; 11-25-2007 at 02:34 PM.

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Currently, you add to the stack
    Code:
    if(number &#37; 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.)
    Last edited by tabstop; 11-25-2007 at 02:52 PM. Reason: Fixed think-o in code

  14. #14
    Registered User
    Join Date
    Sep 2007
    Location
    Arizona
    Posts
    164
    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 &#37; 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)
    Last edited by clegs; 11-25-2007 at 03:21 PM.

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. More fun with the chinese prime number algorigthm
    By kryonik in forum C Programming
    Replies: 4
    Last Post: 09-01-2005, 04:41 PM
  2. Prime Number stops after 29, but why?
    By Daveo in forum C Programming
    Replies: 22
    Last Post: 09-17-2004, 10:55 AM
  3. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM
  4. Random Number problem in number guessing game...
    By -leech- in forum Windows Programming
    Replies: 8
    Last Post: 01-15-2002, 05:00 PM
  5. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-25-2001, 11:45 PM