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::stringstream
s even necessary? - Is there a better way of having
findPrimeFactorization()
output in the form ofw^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)
{
std::stringstream factorsStr;
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";
}
}
return factorsStr.str();
}
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();
}
n
then? \$\endgroup\$