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.


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




#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;cmath&gt;
#include &lt;string&gt;
#include &lt;sstream&gt;

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

string findFactors(unsigned, vector&lt;unsigned&gt; &amp;factors);
string findPrimeFactorization(unsigned posInt);

int main()
{
    unsigned positiveInteger;

    cout &lt;&lt; "\n\n&gt; Pos. Integer: ";
    cin &gt;&gt; positiveInteger;

    vector&lt;unsigned&gt; factors;

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

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

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

string findFactors(unsigned posInt, vector&lt;unsigned&gt; &amp;factors)
{
    std::stringstream factorsStr;
    double sqrtInt = sqrt(static_cast&lt;double&gt;(posInt));

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

    return factorsStr.str();
}

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

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

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

        if (powerDegree &gt;= 1)
        {
            primesStr &lt;&lt; i;

            if (powerDegree &gt; 1)
                primesStr &lt;&lt; '^' &lt;&lt; powerDegree;
            if (i &lt;= posInt)
                primesStr &lt;&lt; " x ";
        }
    }

    return primesStr.str();
}
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 &lt;= 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.