# Simplifying and optimizing factors and prime factorization generator

My first algorithm for finding the factors of a number was pretty slow and horrible (it started at $O(n^2)$, where n was not even the inputted number), but I eventually came up with this new code. I just want the first factors of a number (not the duplicates), so I used sqrt(n) instead of n for the loop. As for the prime factorization, it appears to be efficient but it could probably be improved.

1. Could this program be written simpler and more efficiently?
2. Are all of these std::stringstreams even necessary?
3. Is there a better way of having findPrimeFactorization() output in the form of w^x * y^z?

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <sstream>

using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::stringstream;

string findFactors(unsigned, vector<unsigned> &factors);
string findPrimeFactorization(unsigned posInt);

int main()
{
unsigned positiveInteger;

cout << "\n\n> Pos. Integer: ";
cin >> positiveInteger;

vector<unsigned> factors;

cout << "\n\n  * Factors:\n\n";
cout << findFactors(positiveInteger, factors);

cout << "\n  * Prime Factorization:\n\n      ";
cout << findPrimeFactorization(positiveInteger) << "\n\n\n";

system("PAUSE"); // I use Visual C++
}

string findFactors(unsigned posInt, vector<unsigned> &factors)
{
double sqrtInt = sqrt(static_cast<double>(posInt));

for (unsigned i = 1; i <= sqrtInt; i++)
{
if (posInt % i == 0)
{
factors.push_back(i);
unsigned x = posInt / i;
factorsStr << "      " << i << " x " << x << "\n";
}
}

}

string findPrimeFactorization(unsigned posInt)
{
std::stringstream primesStr;

for (unsigned i = 2; i <= posInt; i++)
{
int powerDegree = 0;

while (posInt % i == 0)
{
posInt /= i;
powerDegree++;
}

if (powerDegree >= 1)
{
primesStr << i;

if (powerDegree > 1)
primesStr << '^' << powerDegree;
if (i <= posInt)
primesStr << " x ";
}
}

return primesStr.str();
}

• What was n then? May 30, 2014 at 5:35
• @Nobody: I'll have to look back at my older code to find that.
– Jamal
May 30, 2014 at 5:37

I have a couple of suggestions that you may wish to consider:

• Don't return a string with the complete statement, return a std::vector/std::map instead with the values, and later assemble the string. It will keep the values in a more usable form and separate out the concerns. You're half doing this with findFactors, go all the way!

• In findPrimeFactorization, your main loop has a terminating condition that varies both sides (i <= posInt), which is a little confusing to reason about. Instead, rewrite it to a while ( posInt != 1 ), which is your actual termination.

• In findPrimeFactorization, to speed things up (slightly) you can try testing 2 separately, then 3, 5, 7... within the loop (other more complex shortcuts are available)

• In terms of writing out the prime factors, you can combine the ideas behind the questions infix_iterator code and std::copy to std::cout for std::pair to get something that's nice, if a little obscure.

• I'll read about std::map first; I've never heard about it before. I'm also unfamiliar with the other std functions, but they're still something to consider. Thanks!
– Jamal
Mar 27, 2013 at 13:20
• Better yet, I'll worry about these std functions at a later time. I have trouble understanding some of the documentation anyway. I did, however, replace the for loop with a while loop in the primes function. It does make more sense now.
– Jamal
Mar 27, 2013 at 19:24
• Sounds a good idea. std::map, vector & list are very useful container classes, learn when you're ready. Any other can wait a while :) Mar 27, 2013 at 22:35
• Alright. :-) I have a feeling I won't cover it in my next programming class, but that isn't a problem. By the end of the class, I should be more familiar with containers. Until then, I'll see if I can adjust my code more.
– Jamal
Mar 27, 2013 at 22:40