Как быстрее всего проверить, являются ли два заданных числа взаимно простыми?

Question

Один из способов — вычислить их НОД и проверьте, равен ли он 1.

Есть ли более быстрый способ?

Answer 1

Алгоритм Евклида (вычисляет gcd) очень быстро.Когда два числа случайно выбираются равномерно из [1, n], среднее количество шагов для вычисления их gcd является O(log n).Среднее время вычислений, необходимое для каждого шага, квадратично по числу цифр.

Существуют альтернативы, которые работают несколько лучше (т. е. каждый шаг субквадратичен по количеству цифр), но они эффективны только для очень больших целых чисел.См., например, Об алгоритме Шенхаге и субквадратичном целочисленном НОД.

Answer 2

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