Разбиение чисел на простые множители

Ну, для гарантии - надо проверить делимость на простые числа до 10^9. Их примерно 48 миллионов - не так уж и много :) Так что можно даже простым перебором по всем простым числам, простите за каламбур.

Ну, и почитайте что-нибудь о факторизации целых чисел.

Update Вот, пользуясь выходным :), набросал программку. На моей машине решетом Эратосфена строит таблицу простых чисел до 1e9 за немного меньше 6 секунд, после чего разлагает на множители числа порядка 9e17 за 0.23с в среднем; минимально - мгновенно (микросекунды), максимально - 0.45 с. Конечно, не скажу, что это быстро, но... Компилировал 64-разрядную программу.

constexpr inline unsigned long pow2(unsigned long i) { return 1 << i; }
inline unsigned long isqrt(unsigned long a)
{
    unsigned long x = a;
    for(unsigned long z = 0; x != z; )
    {
        z = x;
        x = (x + a/x)/2;
    }
    return x;
}
constexpr unsigned long MAX_LIM = 1000000000; //pow2(31) - 1;
constexpr unsigned long ARR_LIM = (MAX_LIM >> 6) + 1;
const     unsigned long SQR_LIM = isqrt(MAX_LIM);;
unsigned long primes[ARR_LIM] = { 0 }; // 0 - простое, 1 - составное
auto set_primes = [](unsigned long idx) { primes[idx >> 6] |= pow2((idx&0x0000003F)>>1); };
auto get_primes = [](unsigned long idx) { return primes[idx >> 6] &  pow2((idx&0x0000003F)>>1); };
vector<unsigned long> Primes;
void makePrimes()
{
    for(unsigned long j = 9; j <= MAX_LIM; j += 3)
    {
        if (j%2) set_primes(j);
    }
    for(unsigned long i = 5; i <= SQR_LIM; i += 6)
    {
        if (get_primes(i)) continue;
        for(unsigned long j = i * i; j <= MAX_LIM; j += i)
        {
            if (j%2) set_primes(j);
        }
    }
    for(unsigned long i = 7; i <= SQR_LIM; i += 6)
    {
        if (get_primes(i)) continue;
        for(unsigned long j = i * i; j <= MAX_LIM; j += i)
        {
            if (j%2) set_primes(j);
        }
    }
    Primes.reserve(55000000);
    Primes.push_back(2);
    for(unsigned long i = 3; i <= MAX_LIM; i+=2)
    {
        if (get_primes(i)) continue;
        Primes.push_back(i);
    }
}

vector<unsigned long> * factors(long long L, vector<unsigned long> * v = 0)
{
    if (v == 0) v = new vector<unsigned long>;
    if (L == 1) return v;
    for(auto f: Primes)
    {
        if (f*f > L) {
            v->push_back(L);
            return v;
        }
        if (L%f == 0)
        {
            v->push_back(f);
            return factors(L/f,v);
        }
    }
    return v;
}

int main(int argc, const char * argv[])
{
    makePrimes();
    printf("Total primes = %d\n",Primes.size());
    for(long long i = 900000000000000000ll; i < 900000000000001000ll; ++i)
    {
        vector<unsigned long> * f = factors(i);
        for(auto x: *f)
        {
            printf("%lu ",x);
        }
        printf("%lld\n",i);
        delete f;
    }
}