GIDForums  

Go Back   GIDForums > Computer Programming Forums > C++ Forum
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read

 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 21-Mar-2010, 10:19
p3rfec7wannabe p3rfec7wannabe is offline
New Member
 
Join Date: Feb 2010
Posts: 12
p3rfec7wannabe is on a distinguished road

Prime Factorization Problems


So my assignment is to type a number and have the program tell the prime factors, but when i type a number in it outputs numbers that are not prime numbers. for example when i put 30 in the program outputs 1,2,3,5,6,10, and 15 are prime factors of 30. i know this is not true and i can not figure out what needs to be changed so that the output is correct.






CPP / C++ / C Code:
#include <iostream>
using namespace std;
int main()
{
   int number;   // declares variable
   
 
   cout<<"This program tells what the prime numbers of a number are."<<endl;
   cout<<"Please enter a number greater than one:"<<endl;
   cin>>number;

  for(int i=1;i<number;i++)  // loop statement	    
	  
	  	  
		 if((number%i)==0)
		{
			cout<<i<<" prime factor of "<< number <<endl;
		}
   
   return 0;
} 
  #2  
Old 21-Mar-2010, 11:18
Blake's Avatar
Blake Blake is offline
Regular Member
 
Join Date: Nov 2005
Posts: 354
Blake is a jewel in the roughBlake is a jewel in the roughBlake is a jewel in the rough

Re: Prime Factorization Problems


You are printing out anything that divides the number entered:

CPP / C++ / C Code:
  if((number%i)==0)
  {
    cout<<i<<" prime factor of "<< number <<endl;
  }

You're not checking if i is prime, so you can't expect only prime numbers to be printed. While you could solve this problem by writing a function to test primality, it would be better to use a recursive approach and avoid the primality test altogether. You could start like this:

CPP / C++ / C Code:
#include <iostream>
using namespace std;

void printPrimeFactors(int number)
{
  for(int i=1;i<number;i++)  // loop statement

		 if((number%i)==0)
		{
			cout<<i<<" prime factor of "<< number <<endl;
		}
}

int main()
{
  int number;   // declares variable
   
 
  cout<<"This program tells what the prime numbers of a number are."<<endl;
  cout<<"Please enter a number greater than one:"<<endl;
  cin>>number;

  printPrimeFactors(number);
   
  return 0;
} 

I've simply created a function for printing prime factors, and pasted your code inside it. As is, it will do exactly the same thing. However, once you code is in this form it is easy to change it into a recursive algorithm. The trick is that when you find an i such that number%i == 0, you can recursively call printPrimeFactors on i and number/i instead of printing i, and then return. If you reach the end of the loop without finding an i such that number%i == 0, then number must by prime, so you should print out number.

Also make sure that your loop starts from 2, not 1.
__________________
www.blake-foster.com
  #3  
Old 21-Mar-2010, 12:01
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 5,496
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: Prime Factorization Problems


Quote:
Originally Posted by p3rfec7wannabe
...what needs to be changed...
Using your existing framework, just make this addition: Once you have found a factor, test to see whether it is a prime number.

A integer greater than 2 is a prime number if it has no factors other than 1 and the number itself.

CPP / C++ / C Code:
int main()
{
    int number;

    cout << "Enter an integer greater than one: ";
    cin >> number;
    if (!cin || number < 2) {
        cout << "Invalid entry." << endl;
        exit(EXIT_FAILURE);
    }

    /*
       Since 1 is a factor of every integer and 1 is
       not a prime number, we need only test for
       factors greater than 1.
     */
    for (int i = 2; i <= number; i++) {/* Find all factors greater than 1 */
        if ((number % i) == 0) {
            /*
               We have determined that "i" s a factor.

               So...

               Do something here to test whether "i" is a prime number.
               Either implement a boolean function, say, isprime(int) that
               returns true if its argument is a prime number, or
               make an inner loop here that sees if there any factors of "i"
               (other than 1 and "i" itself). If it finds any factors with
               this inner loop, then "i" is not a prime number.

               If "i" is a prime number then print it out.
            */
        }
    }

    return 0;
}

A few runs, testing numbers from 2 through 30, might look something like
Code:
Enter an integer greater than one: 2 2 is a prime factor of 2 Enter an integer greater than one: 3 3 is a prime factor of 3 Enter an integer greater than one: 4 2 is a prime factor of 4 Enter an integer greater than one: 5 5 is a prime factor of 5 Enter an integer greater than one: 6 2 is a prime factor of 6 3 is a prime factor of 6 Enter an integer greater than one: 7 7 is a prime factor of 7 Enter an integer greater than one: 8 2 is a prime factor of 8 Enter an integer greater than one: 9 3 is a prime factor of 9 Enter an integer greater than one: 10 2 is a prime factor of 10 5 is a prime factor of 10 Enter an integer greater than one: 11 11 is a prime factor of 11 Enter an integer greater than one: 12 2 is a prime factor of 12 3 is a prime factor of 12 Enter an integer greater than one: 13 13 is a prime factor of 13 Enter an integer greater than one: 14 2 is a prime factor of 14 7 is a prime factor of 14 Enter an integer greater than one: 15 3 is a prime factor of 15 5 is a prime factor of 15 Enter an integer greater than one: 16 2 is a prime factor of 16 Enter an integer greater than one: 17 17 is a prime factor of 17 Enter an integer greater than one: 18 2 is a prime factor of 18 3 is a prime factor of 18 Enter an integer greater than one: 19 19 is a prime factor of 19 Enter an integer greater than one: 20 2 is a prime factor of 20 5 is a prime factor of 20 Enter an integer greater than one: 21 3 is a prime factor of 21 7 is a prime factor of 21 Enter an integer greater than one: 22 2 is a prime factor of 22 11 is a prime factor of 22 Enter an integer greater than one: 23 23 is a prime factor of 23 Enter an integer greater than one: 24 2 is a prime factor of 24 3 is a prime factor of 24 Enter an integer greater than one: 25 5 is a prime factor of 25 Enter an integer greater than one: 26 2 is a prime factor of 26 13 is a prime factor of 26 Enter an integer greater than one: 27 3 is a prime factor of 27 Enter an integer greater than one: 28 2 is a prime factor of 28 7 is a prime factor of 28 Enter an integer greater than one: 29 29 is a prime factor of 29 Enter an integer greater than one: 30 2 is a prime factor of 30 3 is a prime factor of 30 5 is a prime factor of 30

Regards,

Dave
Last edited by davekw7x : 21-Mar-2010 at 13:20.
  #4  
Old 24-Mar-2010, 06:43
p3rfec7wannabe p3rfec7wannabe is offline
New Member
 
Join Date: Feb 2010
Posts: 12
p3rfec7wannabe is on a distinguished road

Re: Prime Factorization Problems


i understand what you are saying but i do not know how to do it. thank you i am going to ask my teacher for help today
  #5  
Old 24-Mar-2010, 21:10
p3rfec7wannabe p3rfec7wannabe is offline
New Member
 
Join Date: Feb 2010
Posts: 12
p3rfec7wannabe is on a distinguished road

Re: Prime Factorization Problems


CPP / C++ / C Code:
#include <iostream>
using namespace std;

int main()
{
    int number;
	cout << "This program takes the prime factors of a number." << endl << endl;
    cout << "Enter a number greater than one: ";
    cin >> number;
    cout << endl;
    

	int i = 2;
	int count = 0;
    while (number > 1)  //if the number is bigger than one the loop while continue to run
	{
        if ((number % i) == 0)
		{ 
			cout << i << "  ";	
			number= number/i;
			count++;

        }
		else i++;
			
	}
	if (count == 1)
	cout << "Prime Number"<< endl;
	cout << endl << endl;
	
    return 0;
}

This is what i came up with. Thank you for the help
  #6  
Old 25-Mar-2010, 07:02
Blake's Avatar
Blake Blake is offline
Regular Member
 
Join Date: Nov 2005
Posts: 354
Blake is a jewel in the roughBlake is a jewel in the roughBlake is a jewel in the rough

Re: Prime Factorization Problems


I didn't want to give away the answer before since this is a school assignment, but since you have solved it now, this is how you would do it recursively (since it never hurts to consider different ways of solving a problem):

CPP / C++ / C Code:
#include <iostream>
using namespace std;

void printPrimeFactors(int number)
{
  for (int i=2; i<number; ++i)
  {
    if (number%i == 0)
    {
      printPrimeFactors(i);
      printPrimeFactors(number/i);
      return;
    }
  }
  cout<<number<<" ";
}

int main()
{
  int number;   // declares variable
   
  cout<<"This program tells what the prime numbers of a number are."<<endl;
  cout<<"Please enter a number greater than one:"<<endl;
  cin>>number;
  cout<<"Prime factors:"<<endl;
  printPrimeFactors(number);
} 
__________________
www.blake-foster.com
  #7  
Old 26-Mar-2010, 12:42
p3rfec7wannabe p3rfec7wannabe is offline
New Member
 
Join Date: Feb 2010
Posts: 12
p3rfec7wannabe is on a distinguished road

Re: Prime Factorization Problems


i like how that works. the code seems to be very simple it just was i didnt learn what printprimefactors was.
 
 

Recent GIDBlogProblems with the Navy (Enlisted) by crystalattice

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Could you explain to me what I have to program about this? disk97 C++ Forum 4 27-Mar-2009 08:34
Will pay through Paypal if somebody helps me. paritoshcool Assembly Language 0 27-Nov-2007 22:27
Python script: Prime numbers crystalattice Python Forum 4 16-Apr-2006 08:19
Chaintech Geforce 5600 FX problems bartster74 Computer Hardware Forum 8 04-May-2004 13:16
Help w/ prime # determination crystalattice C Programming Language 17 18-Apr-2004 21:43

Network Sites: GIDNetwork · GIDWebHosts · GIDSearch · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 19:05.


vBulletin, Copyright © 2000 - 2010, Jelsoft Enterprises Ltd.