Prime factorization

From VT.Prog

Trial division

50% of the integers are divisible by 2, ~33% by three, 25% by four, ... ~88% by a number < 100.

From this, we conclude that a "brute force" approach is useful, albeit in a limited number of cases.

#include <vector>
void factorize(int n, std::vector<int>& factors)
{
    factors.clear();
    
    while (n%2 == 0)
    {
        n /= 2;
        factors.push_back(2);
    }
    
    for (int div=3; div <= n; div+=2)
    {
        while (n%div == 0)
        {
            n /= div;
            factors.push_back(div);
        }
    }
}