범위 [L, R]에서 만들 수 있는 서로소(Co-prime) 쌍의 개수 구하기

이 글에서는 주어진 범위 [L, R] 안에서 만들 수 있는 서로소(co-prime) 쌍의 개수를 구하는 방법을 알아봅니다. 단, 하나의 숫자는 오직 한 개의 쌍에만 포함될 수 있다는 조건이 있습니다.

서로소(Co-prime)란?

서로소란 두 수의 공약수가 1뿐인, 즉 최대공약수(GCD)가 1인 숫자들의 조합을 의미합니다. 예를 들어 3과 4는 공약수가 1뿐이므로 서로소 관계입니다.

예를 들어 하한이 1, 상한이 6이라면 만들 수 있는 서로소 쌍은 다음과 같이 세 가지입니다: (1, 2), (3, 4), (5, 6).

접근 방법

핵심 아이디어는 매우 간단합니다. 바로 연속된 두 자연수는 항상 서로소라는 성질을 이용하는 것입니다. 임의의 정수 n에 대해 n과 n+1의 공약수는 두 수의 차인 1의 약수여야 하므로, 반드시 1뿐입니다. 따라서 범위 내의 숫자들을 차례대로 두 개씩 짝지으면 그 모든 쌍은 자동으로 서로소가 됩니다.

결국 서로소 쌍의 개수는 (R − L + 1) / 2 로 계산할 수 있습니다. 만약 (R − L + 1)이 홀수라면 마지막에 한 개의 숫자가 남아 어떤 쌍에도 속하지 못하고, 짝수라면 범위 내의 모든 숫자가 쌍을 이루게 됩니다.

알고리즘

countCoPrimePairs(L, R)

Begin
    return (R – L + 1)/2
End

C++ 구현 예제

#include <iostream>
using namespace std;
int countCoPrimePairs(int L, int R) {
    return (R - L + 1)/2;
}
main() {
    int l = 1, r = 6;
    cout << "Number of co-prime pairs: " << countCoPrimePairs(l, r);
}

출력 결과

Number of co-prime pairs: 3