범위 [L, R] 내에서 가능한 모든 공동 프라임 고유 요소 쌍?

여기에서 숫자가 단일 쌍 이상으로 나타나지 않는 범위에서 공동 프라임 쌍의 수를 계산하는 방법을 볼 것입니다.

논리를 논의하기 전에 공소수(co-prime number)가 무엇인지 볼까요? 공소수는 양의 정수 제수가 하나뿐인 숫자, 즉 1입니다. 즉, 이 두 숫자의 GCD가 1이라고 말할 수 있습니다.

여기에서 우리는 하한과 상한을 제공합니다. 하한과 상한이 1과 6이면 세 쌍이 있습니다. (1, 2), (3, 4) 및 (5, 6)

이 문제를 해결하기 위한 접근 방식은 다음과 같습니다. 숫자가 연속적이면 항상 공소수입니다. 따라서 개수는 (R – L + 1)/2가 됩니다. (R – L + 1)이 홀수이면 1개의 숫자가 남게 되며, 이는 어떤 쌍에도 속하지 않을 것이고, 이것이 짝수이면 모두가 쌍을 이룰 것입니다.

알고리즘

countCoPrimePairs(L, R)

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

예시

#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