C++ Prime Factorization

I just picked up C++ today and I wonder if this is c++-like. I have a bit of experience with Java.

This is a program that takes a number as input and outputs its prime factorization in no particular order.

Specific questions:

• Am I using std::vector correctly? With all the insert, maybe there is a better way? Similarly, am I using std::map correctly?

• I've never understood what uint_32 is. I understand that it forces the compiler to make the number 32 bits instead of whatever the system decides. Do I need it here?

• Is there anything that a C++ programmer wouldn't do that screams "That only happens in Java/other languages" to you?

Note that I am not worried about efficiency, although if there are improvements, those suggestions are definitely welcome.

#include 
#include 
#include 

std::vector primeFactorize(int n) {
    std::vector result;
    for (int i = 2; i * i > n;
    auto factors = primeFactorize(n);
    // Map is designed 
    std::map factorMap;
    for (int factor : factors) {
        if (factorMap.count(factor) == 0) {
            factorMap[factor] = 1;
        } else {
            ++factorMap[factor];
        }
    }
    bool isFirst = true;
    for (auto keyValuePair : factorMap) {
        if (isFirst) {
            isFirst = false;
        } else {
            std::cout << "*";
        }
        std::cout << keyValuePair.first << "^" << keyValuePair.second;
    }
    return 0;
}

I'll first comment on only C++ usage.

-
vector -- Not exactly sure what you're trying to do by inserting into the front of an array (basically the worst case usage); if you're trying to append, the best way is

result.insert(result.end(), f1.begin(), f1.end());

Vectors are inserted at their end, not front.

map -- std::map is usually implemented as a tree offering O(lgn) queries, not O(1) as you might expect. If you're looking for a hashtable, use std::unordered_map. (however for small use cases and depending on the complexity of the type to hash, map might be faster).

-
uint32_t is an unsigned 32 bit integer. Use it if you want a guarantee on its size, as unsigned int, unsigned long, and the like depends on architecture and compiler. It is not necessary here (more on that later). This might be helpful:

-
On the contrary, you are doing it right by returning a std::vector by value. If it's not copy elisioned out entirely, standard library containers come with move constructors (C++11) that make them more efficient to pass out by value than by reference or pointer as some people are in the habit of doing.

OK onto the comments on style and algorithm

• I personally find it easier to build programs using templates. For example,

template
std::vector primeFactorize(Num n)

is more intuitive for me than a function that's forced to take an int.

• Avoid needless recursion (especially when it splits into 2 subproblems). Prime factorization can be done iteratively (and I'd argue more intuitively).

-
Avoid unbalanced divide and conquer algorithms. Here you're dividing the problem by primeFactorize(i), primeFactorize(n / i), which creates a tiny subproblem and a slightly smaller subproblem, which makes O(lgn) algorithms into O(n).

-
Write comments for yourself to read explaining the algorithm to ensure its correctness and function. For example, when n % i == 0, that means i is a divisor of n. If you wrote that down, you might come to the logical conclusion that you could safely result.push_back(i) and n /= i here instead of the relatively expensive recursion and inserts.

-
Design algorithms that have nice properties, for example that the factors come in sorted order. This prevents you from having to create the map, which seems terribly redundant (apart from perhaps educational uses). The alternative is the sort the factors, then iterate and count consecutive ones, which results in O(nlgn) operations, just as your map solution uses (as it loops through all n factors, and does a lookup in O(lgn) operations).

Here is my example implementation which gives the factors in sorted order using relatively cheap operations.

template 
std::vector factorize(T num) {   // works great for smooth numbers
    vector v;
    if (num = d * d) {
        while (num % d == 0) {  // remove all repeats of this divisor
            v.push_back(d);
            num /= d;
        }
        ++d;
        if (d * d > num && num > 1) { v.push_back(num); return v; }
    }
    return v;
}

Possible optimization suggested by Goswin with removing factors of 2

template 
vector factorize(T num) {    // works great for small prime factors
    vector v;
    if (num >= 1; }   // remove all factors of 2 
    T d {3};
    while (num >= d * d) {
        while (num % d == 0) {  // remove all repeats of this divisor
            v.push_back(d);
            num /= d;
        }
        d += 2;
        if (d * d > num && num > 1) { v.push_back(num); return v; }
    }
    return v;
}

Note that you no longer need to use a std::map to find out how many of each factor there are since this algorithms gives them in sorted order. Using a std::map on top of this would just be an unnecessary layer.

For more straightforward(mostly) implementation of various algorithms (they could be quite educational), check out my simple algorithms library

StackExchange Code Review Q#70880, answer score: 3