Самый эффективный способ найти общие делители двух чисел до 10 ^ 6

Question

Самый эффективный способ найти общие делители двух чисел до 10 ^ 6

Я хотел сохранить все делители всех чисел от 1 до 10 ^ 6. Но это кажется слишком медленным. Это функция preprocess () моего кода:

for(int i=1; i<=1000000; i++)
{
for(int j=1; j<=i/2; j++)
{
if(i%j==0)
divi[i][j] = true;
}
}

Я использовал карту контейнера следующим образом:

map <int, bool> divi[1000010];

Затем я попытался найти общие делители двух заданных чисел.

preprocess();

int T, A, B;

cin >> T;

while(T--)
{
cin >> A >> B;

int common = 0;
for(it = divi[A].begin(); it!=divi[A].end(); it++)
{
if(divi[B][it->first]==true)
common++;
}

cout << common << endl;

Как мне подойти сейчас, чтобы сделать это достаточно быстро?

0

c++factors time-complexity

Решение

Другие решения

Это зависит от того, что вы хотите: если вы хотите только общие делители для некоторых конкретных чисел, то решение Евклидова алгоритма является решением.

Если вы действительно хотите получить список всех делителей для всех чисел 1..n, одним из решений будет (похоже на сито):

  for(int I=1;I<=sqrt(n);++I) {
for(int j=I;j*I<=n;++j) divi[I*j][j]=divi[I*j][I]=true;
}

Сложность кода исходного кода — O (N ^ 2) с первым ответом — O (N ^ 1.5). Я считаю, что новая формула O (N * log N)

1

Источник

Accepted Answer

Помимо того, что с помощью std::map само по себе будет дорого (разве вы не можете использовать массивы?), быстрый числовой выигрыш заключается в том, чтобы подняться только до квадратного корня из числа во внутреннем цикле.

for (int j = 1; j * j <= i; j++)

(Отмечая, что квадрат j дешевле, чем вычисление квадратного корня iи удерживает вас от вычислений с плавающей запятой.)

Это должно сочетаться с замечанием, что если j это делитель, то i / j является также делитель Таким образом, вы также должны заменить

divi[i][j] = true;

с

divi[i][j] = divi[i][i / j] = true;

Эта оптимизация сосредоточена вокруг вычисления делителей не замужем число. Есть более быстрые подходы для получения делителей для задавать чисел, но мой подход может быть достаточно. Даунвот, если нет.

4