By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,851 Members | 2,097 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,851 IT Pros & Developers. It's quick & easy.

prime factoring progam giving me problems

P: 6
I need to print out the prime numbers of an integer entered in. I am new to C++ but wrote this program with my partner and while it compiles, that's about all it does. I'm pretty sure it gets lost in the for loop, or atleast that's where I get lost.
Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int main()
  5.  
  6. {
  7. int valueToFactor;
  8.  
  9. cout << "Enter Number to Factor: "<< endl;
  10. cin >> valueToFactor;
  11.  
  12.  
  13.  
  14. for(int n=2; n <= valueToFactor;){
  15.     if(valueToFactor%n == 0){
  16.  
  17.         cout << "The Prime Factors are:" << n << endl;
  18.         valueToFactor = valueToFactor/n;
  19.     }
  20.      else 
  21.  
  22.     ++n;
  23.     }
  24.  
  25. return(0);
  26. }
  27.  

I was wondering if anyone had any hints to get me moving again.
Thanks.
RyeGuy
Mar 20 '07 #1
Share this Question
Share on Google+
12 Replies


sicarie
Expert Mod 2.5K+
P: 4,677
I need to print out the prime numbers of an integer entered in. I am new to C++ but wrote this program with my partner and while it compiles, that's about all it does. I'm pretty sure it gets lost in the for loop, or atleast that's where I get lost.
Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int main()
  5.  
  6. {
  7. int valueToFactor;
  8.  
  9. cout << "Enter Number to Factor: "<< endl;
  10. cin >> valueToFactor;
  11.  
  12.  
  13.  
  14. for(int n=2; n <= valueToFactor;){
  15.     if(valueToFactor%n == 0){
  16.         cout << "The Prime Factors are:" << n << endl;
  17.         valueToFactor = valueToFactor/n;
  18.     }
  19.      else 
  20.     ++n;
  21.     }
  22. return(0);
  23. }
  24.  
I was wondering if anyone had any hints to get me moving again.
Thanks.
RyeGuy
You only increment n in the 'else' statement, which means that if you enter the 'if' portion, n stays the same through the loop (as soon as it's even, it gets stuck). You could just increment n no matter what, and print out each factor individually.
Mar 20 '07 #2

Roonie
P: 99
well, i have two things to mention.

first off, it doesnt look like youre set up to count in primes. it looks like youre trying to use the iterator for your for loop to factor the input number when you need to use a different variable. (youre counting by 2,3,4,5,6, . . . and you need to be factoring by 2,3,5,7,11, . . . )

i think you also need some sort of data structure to hold the factors youve already found so far too. you need to keep track of how many times you can divide by two, and then three, and five . . . etc.
Mar 20 '07 #3

P: 6
You only increment n in the 'else' statement, which means that if you enter the 'if' portion, n stays the same through the loop (as soon as it's even, it gets stuck). You could just increment n no matter what, and print out each factor individually.


I was thinking of this, you mean increment it in the for loop? I'm not sure how i would get each factor to print out then.
Mar 20 '07 #4

sicarie
Expert Mod 2.5K+
P: 4,677
I was thinking of this, you mean increment it in the for loop? I'm not sure how i would get each factor to print out then.
I would recommend a for loop - then you can specify an action for each separate iteration of that loop.

Also look at Roonie's post - I think you're missing something with your algorithm, you're only counting the divisors, not the primes (though I think that would be the first step, if you stored those, then you could find the ones that were primes with an extra iteration),
Mar 20 '07 #5

P: 6
well, i have two things to mention.

first off, it doesnt look like youre set up to count in primes. it looks like youre trying to use the iterator for your for loop to factor the input number when you need to use a different variable. (youre counting by 2,3,4,5,6, . . . and you need to be factoring by 2,3,5,7,11, . . . )

i think you also need some sort of data structure to hold the factors youve already found so far too. you need to keep track of how many times you can divide by two, and then three, and five . . . etc.
Thanks For the quick responses!

Roonie would it be easier for me to have n start at 1 and then increments by 2? Also I am not sure how I would add something to hold the prime factors, sorry im not understanding very much, this is all new to me.
thanks again.
ryeguy
Mar 20 '07 #6

sicarie
Expert Mod 2.5K+
P: 4,677
Thanks For the quick responses!

Roonie would it be easier for me to have n start at 1 and then increments by 2? Also I am not sure how I would add something to hold the prime factors, sorry im not understanding very much, this is all new to me.
thanks again.
ryeguy
An integer array would be able to store the numbers - it depends on what else you want to do with them, but I'm pretty sure an array would be easiest.
Mar 20 '07 #7

Roonie
P: 99
yeah, i would say that an int[] where each successive member represented how many times each of the primes factored would do nicely to store that information.

and as for counting in primes, that is something that professional computer programmers try to solve in their work. is there any upper limit to your input? if so, it might be easiest to simply hard-code the primes up to that limit. if not, im sure i can scratch up a reference or two to some prime-number finders . . .
Mar 20 '07 #8

P: 6
An integer array would be able to store the numbers - it depends on what else you want to do with them, but I'm pretty sure an array would be easiest.
I just recently learned about arrays but wouldn't i need to know how many prime integers there were to start the array?
Mar 20 '07 #9

P: 6
yeah, i would say that an int[] where each successive member represented how many times each of the primes factored would do nicely to store that information.

and as for counting in primes, that is something that professional computer programmers try to solve in their work. is there any upper limit to your input? if so, it might be easiest to simply hard-code the primes up to that limit. if not, im sure i can scratch up a reference or two to some prime-number finders . . .

I'm not sure if there was meant to be an upper limit but there was none given.
Mar 20 '07 #10

sicarie
Expert Mod 2.5K+
P: 4,677
I just recently learned about arrays but wouldn't i need to know how many prime integers there were to start the array?
You can always grow the array dynamically...it would be annoying, but you could do it.

You could also use a vector, or even a list, which are designed to be able to be added to on the fly, but requires contiguous free memory space.
Mar 20 '07 #11

Roonie
P: 99
yeah, i dont think there is any better way to dynamically grow a simple array than to simply copy the small array to a new, bigger array. if youre unsure how much data you have to cope with, i would definitely suggest using a more advanced data type.

as for a good way to find prime numbers, im looking. i think how you do it really depends on how much processing time you can devote to finding a prime number. if this is something that "just has to work" you can write an algorithm to brute-force it. what sort of a program are you writing?

i dunno, im on google right now . . . i seem to remember something about a guy named fermat in conjunction with primes? . . . its been a while since ive needed prime numbers too.
Mar 20 '07 #12

P: 6
yeah, i dont think there is any better way to dynamically grow a simple array than to simply copy the small array to a new, bigger array. if youre unsure how much data you have to cope with, i would definitely suggest using a more advanced data type.

as for a good way to find prime numbers, im looking. i think how you do it really depends on how much processing time you can devote to finding a prime number. if this is something that "just has to work" you can write an algorithm to brute-force it. what sort of a program are you writing?

i dunno, im on google right now . . . i seem to remember something about a guy named fermat in conjunction with primes? . . . its been a while since ive needed prime numbers too.

Hey thanks for your help, i figured a program out late last night!

thanks
ryan
Mar 20 '07 #13

Post your reply

Sign in to post your reply or Sign up for a free account.