Увеличение быстродействия

[-=M{a}LoY=-]

Добрый вечер.
Задача относительно простая : найти все делители числа 600851475143. Но если делать в лоб, то это занимает ужасно много времени.
Подскажите, как можно увеличить быстродействие такой программки.

[Utkin]

Ну собственно все числа кроме нуля, это если без спецслучаев . Или Вы имеете ввиду целые делители для получения целого числа? Тогда рассматривайте только нечетные. Далее - данное число не делится на 3 (сумма всех цифр числа не делится на три). Это значит, что данное число не будет делится на все числа, которые можно без остатка поделить на 3. То есть не будет делится на 9, 12, 15, 18 и т.д. Не будет делится на 4, потому что четное. Число не делится на 5, а значит не будет делиться и по аналогии с 3-кой - на 10, 15, 20, 25 и т.д. Тенденция ясна? Совершенно очевидно, что нужно пытаться делить только на такие числа, которые делятся на самих себя. Кроме того, я подозреваю что и данное число является простым - то есть делится только на само себя (ну и единицу естественно ибо на нее все делится) .

--ДОБАВЛЕНО---
Делится: 71*839*1471*6857

[-=M{a}LoY=-]

Спасибо) Суть ясна
А вот если увеличивать быстродействие по средством увеличения выделяемой для этой задачи памяти или что то подобное этому?)
Может я не совсем правильно выразился, я только учусь
Надеюсь поймете, что я хочу

[Axrik]

Вот памяти как раз таки нужно выделять ровно столько сколько нужно, не больше, не меньше. Выделение лишней памяти наоборот будет тормозить выполнение.

[Utkin]

Вы сначала составьте алгоритм без учета аппаратных требований.

[Kostia]

Наваял нечто такое:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    vector<size_t> simple_numbers = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
                                     61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131,
                                     137, 139, 149, 151, 157};
    simple_numbers.reserve(50);
    size_t X = 137814600;
    size_t sqrt_X = sqrt(X) + 1;
    size_t Last = X;
    while(X > 1)
    {
        for(size_t i = 0; i < simple_numbers.size(); i++)
        {
            if(simple_numbers[i] > sqrt_X)
            {
                cout << X << " ";
                X = 1;
                break;
            }
            switch(i)
            {
            case 0:
                if(!(X & 1))
                {
                    cout << 2 << " ";
                    X /= 2;
                    i = simple_numbers.size();
                }
            break;
            default:
                if(!(X % simple_numbers[i]))
                {
                    cout << simple_numbers[i] << " ";
                    X /= simple_numbers[i];
                    i = simple_numbers.size();
                }
            break;
            }
        }
        if(X == Last)
        {
            size_t d = simple_numbers[simple_numbers.size()-1];
            do
            {
                d++;
                if(d > sqrt_X)
                {
                    d = X;
                    X = 1;
                    break;
                }
            }
            while(X % d);
            if(X > 1)
            {
                X /= d;
                //simple_numbers.push_back(d); ??
            }
            cout << d << " ";
        }
        sqrt_X = sqrt(X) + 1;
        Last = X;
    }
    return 0;
}

Правда сомневаюсь в работоспособности некоторых моментов, но в целом вроде работает. Сомнения вызывают закомментированная строчка ??, вроде как ее можно раскомментить и все будет работать хорошо.

Советую почитать книгу: http://www.ozon.ru/context/detail/id/4893803/

[-=M{a}LoY=-]

Ооо ... спасибо ) Буду разбираться
За книгу отдельное спасибо