Нахождение всех множителей большого числа в заданном диапазоне

Есть непростое число где-то между 796200000 и 796400000, какой есть наиболее быстрый способ найти все его делители? (в идеале с реализацией) (нужны именно делители, для последующего их использования)
Нет, в гугле меня не забанили, но я не смог быстро разобраться в невероятном разнообразии алгоритмов.
Заранее спасибо.

Ответ

Ну, как мне кажется - найти разложение на простые множители, а затем находить все возможные сочетания простых сомножителей в непростые.
Чтобы найти все простые, достаточно проверить делимость на простые, не большие 28284 (квадратный корень из максимального числа). Чтобы найти все простые - можно заранее то же решето Эратосфена использовать, с проверкой до 168 (очередной квадратный корень).
Что-то типа
vector primus(int max) { vector p { 2 }; vector prime(max+1, true); prime[0] = prime[1] = false; for(int i = 3; i<= max; i += 2) if (prime[i]) { p.push_back(i); if (i*i <= max) for(int j= i*i; j <= max; j+=i) prime[j] = false; } return p; }
int main(int argc, const char * argv[]) { vector p = primus(28300);
int N = 796400000; for(size_t i = 0; i < p.size() && N > p[i]; ++i) { while (N%p[i] == 0) { cout << p[i] << endl; N /= p[i]; } } if (N > 1) cout << N << endl; }
Окончательная полная программа получения всех (не только простых!) делителей всех указанных чисел у меня на машине делает это за 2-3 секунды.