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

#cpp #алгоритм #простые_числа

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

Нет, в гугле меня не забанили, но я не смог быстро разобраться в невероятном разнообразии
алгоритмов.

Заранее спасибо.
    

Ответы

Ответ 1

Ну, как мне кажется - найти разложение на простые множители, а затем находить все
возможные сочетания простых сомножителей в непростые.

Чтобы найти все простые, достаточно проверить делимость на простые, не большие 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 секунды.


Ответ 2

Заранeе прогнать 200 000 чисел и составить табличку. 200 килобайт есть у всех.

P.S. Да, я знаю, что при желании можно это ужать в 8 раз, пакуя в биты

P.P.S. Да, я знаю, что если хранить все с выравниванием, получится не 200 кило, а
метр. Не страшно.


Ответ 3

Чтобы найти все делители, надо искать только делители до корня из числа, а остальные
получаются делением числа не его делитель. Осторожно обработать числа, являющиеся полными
квадратами. В общем-то всё.

http://ideone.com/akXlLV - 5К чисел за 3 секунды

vector  getDivs(int n) {
  int q;
  vector  res;

  for (q=1; q*q
Ответ 4

Разложение на множители.

#include 
#include 
using namespace std;

/*
    Функция получения делителей числа N
    N - начальное число
    &divisor - ссылка на вектор, куда запишут результат
*/
void getDivisor(int N, vector& divisor){
    int i = 2;
    while(N!=1){
        if(N % i == 0){
            N /= i;
            divisor.push_back(i);
        } else {
            ++i;
        }
    }
}

int main() {
    int N;
    vector divisor;
    cin >> N;

    getDivisor(N, divisor);

    for(int i=0; i