Finding the prime factors of a number

Question

I am trying to write a program which, given a number as an input, prints the prime factors AND the exponents of the prime factors of that number.

Example:

Input:

20

Output:

2^2 5^1

And this is the code that I've come up with:

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>

std::vector<int>factors;
std::map<int,int>factormap;

int main()
{
    int n;
    scanf("%d",&n);

    for(int i = 2; i < n + 1; i++)
    {
        while(n%i < 1)
        {
            //Populate a vector of integers with the prime factors of the given number
            factors.push_back(i);
            n /= i;
        }
    }

    for(int i = 0; i < factors.size(); i++)
    {

        if(factormap.count(factors[i]) == 0)
        {
            //If the number hasn't been added yet, add it to the std::map
            //map is designed this way: <number, how many times it appears>
            factormap.insert(std::pair<int,int>(factors[i],std::count(factors.begin(), factors.end(), factors[i])));
        }            
    }

    for(std::map<int,int>::iterator it=factormap.begin(); it != factormap.end(); ++it)
    {
        printf("%d^%d ", it->first, it->second);
    }
    printf("\n");

}

And it works as I intended but I feel like I'm putting too much effort into this. Is there an easier and more elegant way to accomplish this?

Answer 1

My first thought was that there wasn't much that you could do. However, it does occur to me that you don't need to have both the vector and map variables.

private std::map<int,int> count_for;

protected void count_factors(int &n, int factor) {
    // if factor is not actually a factor of n, nothing to do
    if ( n % factor != 0 ) {
        return;
    }

    // initialization only needs to be done once, 
    // so do it before the loop
    // we already checked that this is a factor and should be in the map
    count_for[factor] = 0;
    do {
        count_for[factor]++;
        n /= factor;
    } while ( n % factor == 0 );
}

public void generate_factors(int n) {
    // handle the only even prime separately
    count_factors(n, 2);

    // note that if a particular value of i is not prime,
    // then it won't divide n evenly
    // as we will have removed all its factors from n already
    for ( int i = 3; i <= n; i += 2 ) {
        count_factors(n, i);
    }
}

public ostream & display(ostream &out) {
    for ( const auto &p : count_for ) {
        out << p.first << "^" << p.second << " ";
    }
    out << endl;
}

I don't have a C++ compiler at the moment, so I haven't tested any of this.

Some other comments. Note that I put those functions in a class. That gets us away from the global variables of the original program and puts the code in a more sustainable location. We can reuse the code in other programs easily.

When doing comparisons in a loop, you want to minimize the number of operations. Thus, i <= n is better than i < n + 1. Similarly, try to avoid making function calls as in i < factors.size(). If the result won't change during the loop, do the function call in the loop initialization, like so

for ( int i = 0, m = factors.size(); i < m; i++ )

When doing a modulus operation, there's one special result 0. I don't know that there's a way to get a negative result, but if there is, you don't want one. So write it as you mean it n % i == 0 not n % i < 1. Note that this would be different if you were doing something like

for ( int i = n; i >= 0; i-- ) {
    // do stuff with i
}

Then you'd want to guard against i changing in addition to the decrement, so you use the inequality.

        factormap.insert(std::pair<int,int>(factors[i],std::count(factors.begin(), factors.end(), factors[i])));

That's an awful lot of things happening in one line. It's often easier to read something like that if you assign the results of the function calls to variables rather than chaining them like that. Also, some errors won't do a good job of identifying what prompted them, but they'll usually tell you the right line.

If you're using a C++11 compiler, then you can use range-based for loops. If not, then stick with your original iterator approach.

The printf function comes from C. While it will work in C++, the C++ way is to use std::cout. I used a display function, but you could also overload the << operator to similar but more flexible effect.