Prime Factors

This is a discussion on Prime Factors within the C++ Programming forums, part of the General Programming Boards category; I have a program that will find prime factors of any input number Code: #include <iostream> using namespace std; int ...

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    23

    Prime Factors

    I have a program that will find prime factors of any input number

    Code:
    #include <iostream>
    
    using namespace std;
    
    int main()
    {
    	int n;
    
    	cout << "Enter the number to factor:" << endl;
    	cin >> n;
    
    	int k=2;
    
    	cout << "The prime factors of " << n << " are: " << endl;
    
    	while (n > k*k)
    	{
    		if ((n%k)==0)
    		{
    			n=(n/k);
    
    			cout << k << " ";
    
    		}
    
    		else
    		{k=k+1;
    		}
    	}
    	cout << n << " ";
    }

    Now, say I put in 567 as the number to factor, the output would be 3 3 3 3 7

    However, if I want to switch that output to the format 3^4 7, I'm not really sure how to go about doing that.

    Any help I can get would be great

    Thanks

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,340
    You could keep track of how many times a value k divides evenly. When it no longer divides evenly, output that value and if the count is higher than 1 output ^ and the count.

  3. #3
    Registered User
    Join Date
    Oct 2007
    Posts
    23
    Quote Originally Posted by Daved View Post
    You could keep track of how many times a value k divides evenly. When it no longer divides evenly, output that value and if the count is higher than 1 output ^ and the count.

    I'm not sure how to keep track of something like that though, however, that is the same idea I had.

    Wait, I could go n/k= first

    And then output would be cout << k << " ^ " << "first"

    I'll have to work with that a bit

    Edit: but it's not n/k, it's how many times that process is repeated...
    Last edited by Adrian; 10-02-2007 at 06:12 PM.

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,340
    But you are doing them in order, so that if you find a factor k then you know it is greater or equal to the previous factor. If it is equal, then bump up the count, if not, reset the count. Only output k (and the count) when k is incremented and the count is not zero.

    To see it more clearly, follow your current code through an example. Write down each step as it happens (make it a small example, like 12). Notice where you are in the code when you stop finding a particular factor. See if that helps you figure out where and how to count.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 02-19-2009, 09:32 PM
  2. Replies: 3
    Last Post: 03-29-2005, 03:24 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Finding prime factors
    By ripper079 in forum C Programming
    Replies: 3
    Last Post: 05-17-2002, 09:23 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21