# 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:

1. Am I using std::vector correctly? With all the insert, maybe there is a better way? Similarly, am I using std::map correctly?
2. 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?
3. 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 <iostream>
#include <vector>
#include <map>

std::vector<int> primeFactorize(int n) {
std::vector<int> result;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
auto f1 = primeFactorize(i), f2 = primeFactorize(n / i);
result.insert(result.begin(), f1.begin(), f1.end());
result.insert(result.begin(), f2.begin(), f2.end());
return result;
}
}
result.push_back(n);
return result;
}

int main(int argc, char** argv) {
int n;
std::cin >> n;
auto factors = primeFactorize(n);
// Map is designed <factor, exponent>
std::map<int, int> 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.

1. 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).

2. 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:

3. 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

1. I personally find it easier to build programs using templates. For example,
template <typename Num> std::vector<Num> primeFactorize(Num n)
is more intuitive for me than a function that's forced to take an int.
2. Avoid needless recursion (especially when it splits into 2 subproblems). Prime factorization can be done iteratively (and I'd argue more intuitively).
3. 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).

4. 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.

5. 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 <typename T>
std::vector<T> factorize(T num) {   // works great for smooth numbers
vector<T> v;
if (num < 4) { v.push_back(num); return v; }
T d {2};
while (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 <typename T>
vector<T> factorize(T num) {    // works great for small prime factors
vector<T> v;
if (num < 4) { v.push_back(num); return v; }
while ((num & 1) == 0) { v.push_back(2); 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

• unit_32 on item 2 of the first list is a typo, I believe? Probably meant to be uint32_t? Nov 26 '14 at 14:24
• I disagree with point 1, and point 3 is completely wrong. Nov 26 '14 at 15:21
• Point 3 is in so far right as that i can never be factorized. That's why it can be pushed directly. Doing a divide & conquer with that split makes no sense. Nov 26 '14 at 17:06
• Optimizations: 1) After testing for 2 as factor no more even numbers need to be tested. A similar trick can be used to avoid multiples of 3. 2) The original code generated prime factors with exponents. This code adds duplicate prime factors. Instead of adding the factor in the inner loop count the number of times num can be devided by a factro and then add std::pair(num, count). Nov 26 '14 at 17:10
• @Yuushi can you explain why point 3 is wrong? @Goswin The optimization for even numbers is a good point. I wrote my version mainly for the purpose of being straightforward to describe a simple algorithm that results in desirable qualities (adds duplicate factors and they are in order). Because they are in order, duplicates are adjacent, hence removing the need to use std::pair, which I feel is an unnecessary layer. Nov 27 '14 at 2:19

## Use const auto & with a range-for

When you're iterating over a range in C++, it's often best to use const auto & for the type of the individual values. For example, in this code, instead of this:

for (int factor : factors) {
if (factorMap.count(factor) == 0) {
factorMap[factor] = 1;
} else {
++factorMap[factor];
}
}


the code could instead be written like this:

for (const auto &f : factors)
++factorMap[f];


Using this method, the code is somewhat simplified and it also won't need to be rewritten if you decide to factor long numbers instead of ints. It doesn't matter much with objects that are "cheap" to copy, such as an int, but with longer data structures with more costly copy constructors, you'll be able to avoid unneeded copies by using const auto &, which will speed up the code. Unlike Java, in C++ we tend to think carefully about memory usage since it's completely under the control of the programmer and can often result in significant speed improvements if code is carefully structured.

## Think carefully about signed versus unsigned

If I attempt to factor the number -24 with this code, it incorrectly factors this as -24^1. If your code is only intending to be able to handled unsigned numbers, you should change the function so that it only accepts unsigned numbers. In my case, I changed the code to this:

std::vector<unsigned long> primeFactorize(unsigned long n) { /* ... */ }


## Avoid introducing unnecessary variables

The code currently prints the results with this:

bool isFirst = true;
for (auto keyValuePair : factorMap) {
if (isFirst) {
isFirst = false;
} else {
std::cout << "*";
}
std::cout << keyValuePair.first << "^" << keyValuePair.second;
}


This works, but it uses a variable isFirst which isn't really needed, and is checked every loop iteration. An alternative would be to use an iterator; in this case we can (and should) use a const iterator:

auto fm = factorMap.cbegin();
std::cout << fm->first << '^' << fm->second;
for (++fm ; fm != factorMap.cend(); ++fm)
std::cout << " * " << fm->first << '^' << fm->second;
std::cout << '\n';


## Consider using a template for metaprogramming

If we want to modify the code to factor long integers or unsigned long integers, we'd have to change a number of places in the code. However, using templates, which you may also have used in Java, we can isolate the change:

template <typename T>
std::vector<T> primeFactorize(const T &n) {
std::vector<T> result;
for (T i = 2; i * i <= n; ++i) {
if (n % i == 0) {
auto f1 = primeFactorize(i), f2 = primeFactorize(n / i);
result.insert(result.begin(), f1.begin(), f1.end());
result.insert(result.begin(), f2.begin(), f2.end());
return result;
}
}
result.push_back(n);
return result;
}


Now when we want to call this routine, we can use something like this:

auto factors = primeFactorize<unsigned long>(n);


Note that the templated version uses const T & as the type. Again, this is because doing so can save unnecessary copying in the case that the number is something more costly to copy.

## Use cbegin and cend when possible

Using the constant versions of iterators (and const in general) is a good idea where possible. It makes your code a little safer and sometimes a little faster as well. In this code, we can use it like this:

        result.insert(result.begin(), f1.cbegin(), f1.cend());
result.insert(result.begin(), f2.cbegin(), f2.cend());


There is nothing inherently wrong with your algorithm, but it could be made more efficient in a number of small ways. First, the code compares i * i <= n every time through the loop. Rather than doing a new multiplcation every time, why not just calculate sqrt(n) once before the loop and then compare it to i. Similarly, all prime factors of any number are odd except 2. This suggests that we can check divisibility by 2 once, then check for 3 and increment by 2 each iteration. Further, the first factor we find is always going to be prime, so there's no reason to call primeFactorize(i) -- we can simply do result.push_back(i) instead.
## Omit return 0
When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no reason to put return 0; explicitly at the end of main.
• I disagree with your last point. If a method or function has a non-void return type then the last should always be a return. It makes clearer what the intention of the function is. This is true for main. Nov 27 '14 at 8:11
• @CodeClown: Section 3.6.1 of the C++ standard says, "If control reaches the end of main without encountering a return statement, the effect is that of executing return 0;" Nov 27 '14 at 10:27