C++에서 1에서 N까지 정렬되지 않은 co-prime 쌍의 수를 계산하는 쿼리

이 문제에서는 각각 숫자 N을 포함하는 Q 쿼리가 제공됩니다. 우리의 임무는 C++에서 1에서 N까지 정렬되지 않은 coprime 쌍의 수를 계산하는 쿼리를 푸는 프로그램을 만드는 것입니다.

공동 프라임 상대적 소수 또는 상호 소수라고도 하는 것은 단 하나의 인수, 즉 1을 갖는 숫자 쌍입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 :Q =2, 쿼리 =[5, 6]

출력 :10

설명

쌍은 다음과 같습니다. (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5),(3, 4 ), (3, 5), (4, 5)

솔루션 접근 방식

이 문제에 대한 가장 유망한 솔루션은 오일러의 TotientFunction phi(N)을 사용하는 것입니다. phi(N)은 주어진 값 N까지 co-prime의 총 수를 계산합니다. 오일러의 totient 함수는 다음과 같습니다.

$$𝛷(𝑁) =𝑁 ∏𝑁/𝑁 (1 −),$$

여기서 p는 N의 모든 소인수입니다.

이제 N까지 정렬되지 않은 coprime 쌍의 개수 값을 미리 계산합니다. 그런 다음 미리 계산된 배열에서 각 쿼리의 값을 찾습니다.

예시

#include <iostream>
using namespace std;
#define N 10001
int phi[N];
int CoPrimePairs[N];
   void computePhi(){
      for (int i = 1; i < N; i++)
         phi[i] = i;
      for (int p = 2; p < N; p++) {
      if (phi[p] == p) {
         phi[p] = p - 1;
         for (int i = 2 * p; i < N; i += p) {
            phi[i] = (phi[i] / p) * (p - 1);
         }
      }
   }
}
void findCoPrimes() {
   computePhi();
   for (int i = 1; i < N; i++)
      CoPrimePairs[i] = CoPrimePairs[i - 1] + phi[i];
}
int main() {
   findCoPrimes();
   int Q = 3;
   int query[] = { 5, 7, 9};
   for (int i = 0; i < Q; i++)
      cout<<"For Query "<<(i+1)<<": Number of prime pairs is "<<CoPrimePairs[query[i]]<<endl;
   return 0;
}

출력

For Query 1: Number of prime pairs is 10
For Query 2: Number of prime pairs is 18
For Query 3: Number of prime pairs is 28