주어진 두 개의 숫자가 공동 정보인지 확인하는 가장 빠른 방법은 무엇입니까?

Question

한 가지 방법은 계산하는 것입니다 GCD 그리고 그것이 1인지 확인하십시오.

더 빠른 방법이 있습니까?

Answer 1

유클리드 알고리즘 (계산 gcd)는 매우 빠릅니다. 두 숫자가 무작위로 균일하게 그려 질 때 [1, n], 계산하기위한 평균 단계 수 gcd ~이다 O(log n). 각 단계에 필요한 평균 계산 시간은 숫자 수에서 2 차입니다.

다소 더 나은 성능을 발휘하는 대안이 있습니다 (즉, 각 단계는 숫자의 수에 따라 각 단계가 적절하다) 그러나 매우 큰 정수에서만 효과적입니다. 예를 들어, Schönhage의 알고리즘 및 하위 정수 정수 GCD 계산에.

Answer 2

디비전/나머지가 교대보다 훨씬 비싸지 않은 기계에서 실행중인 경우 고려하십시오. 이진 GCD.