Simple Factor Class

I have a class which lazily factors numbers. It provides the user with these methods:

1. getFactors returns a vector<unsigned int> containing the argument's factors
2. getFactorCount returns the number of an argument's factors
3. compareFactors takes 2 arguments returning a negative integer if the 1^st argument has fewer factors, a positive number if the 2^nd argument has fewer factors, and a 0 if the arguments have the same number of factors
4. findNextPrime returns the next prime after the current number
5. gcd returns the Greatest Common Denominator of its arguments
6. lcm returns the Least Common Multiple of its arguments

I welcome general advice on the class, but I have specific concerns in these areas:

1. I'm varying a lot of extra memory to maintain the index of a numbers next factor as the my vector becomes large
2. I have to reconstruct the vector of factors for every method I provide that seems expensive time wise

Is there a way that I could structure my data differently to avoid such costs?

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <utility>
#include <vector>

using namespace std;

class Factor {
    vector<pair<unsigned int, size_t>> factors;

    void factor(const unsigned int input) {
        auto i = 2U;

        while (input % i != 0U) {
            ++i;
        }

        const auto second = input / i;

        factors[input] = make_pair(i, second);

        if (second >= 2 && factors[second].first == 0U) {
            factor(second);
        }
    }
public:
    vector<unsigned int> getFactors(unsigned int input) {
        if (input <= 1) {
            return vector<unsigned int>{};
        } else if (input >= size(factors)) {
            factors.resize(input + 1U);
            factor(input);
        } else if (factors[input].first == 0U) {
            factor(input);
        }

        vector<unsigned int> result;

        do {
            result.push_back(factors[input].first);
            input = factors[input].second;
        } while (factors[input].first != 0U);

        return result;
    }

    size_t getFactorCount(const unsigned int input) {
        return size(getFactors(input));
    }

    int compareFactors(const unsigned int lhs, const unsigned int rhs) {
        return getFactorCount(lhs) - getFactorCount(rhs);
    }

    unsigned int findNextPrime(unsigned int input) {
        if (++input == 1U) {
            return 1U;
        }

        do {
            if (input >= size(factors)) {
                factors.resize(input + 1U);
            }

            if (factors[input].first == 0U) {
                factor(input);
            }
        } while (factors[input++].second != 1U);

        return input - 1U;
    }

    unsigned int gcd(const unsigned int lhs, const unsigned int rhs) {
        vector<unsigned int> result;
        const vector<unsigned int> lhsFactors = getFactors(lhs);
        const vector<unsigned int> rhsFactors = getFactors(rhs);

        set_intersection(cbegin(lhsFactors), cend(lhsFactors), cbegin(rhsFactors), cend(rhsFactors), back_inserter(result));

        return accumulate(cbegin(result), cend(result), 1U, multiplies<unsigned int>());
    }

    unsigned int lcm(const unsigned int lhs, const unsigned int rhs) {
        const vector<unsigned int> lhsFactors = getFactors(lhs);
        const vector<unsigned int> rhsFactors = getFactors(rhs);
        const auto it = find_first_of(cbegin(lhsFactors), cend(lhsFactors), cbegin(rhsFactors), cend(rhsFactors));

        return it == cend(lhsFactors) ? 1U : *it;
    }
};

I've included some testing demonstrating class functionality here: http://ideone.com/njH34A