Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

주어진 숫자들이 서로소인지 확인하는 C++ 프로그램

문제 정의

정수 n개가 담긴 배열 nums가 주어졌다고 가정해 봅시다. 이때 배열 안의 숫자들이 쌍별 서로소(pairwise coprime)인지, 집합별 서로소(setwise coprime)인지, 아니면 서로소가 아닌지 판별해야 합니다.

  • 쌍별 서로소(pairwise coprime): 두 수 nums[i]와 nums[j]의 최대공약수가 gcd(nums[i], nums[j]) = 1일 때 이 두 수는 서로소입니다. 배열 내 모든 숫자 쌍(i < j)에 대해 이 조건이 성립해야 합니다.

  • 집합별 서로소(setwise coprime): 배열 전체 숫자들의 최대공약수가 1일 때 집합별 서로소라고 합니다.

  • 두 조건 중 어느 것도 만족하지 않으면 서로소가 아님(not coprime)이라고 합니다.

예를 들어 n = 4, nums = {7, 11, 13, 17}이 입력으로 주어지면 출력은 "숫자들은 쌍별 서로소입니다"가 됩니다. 배열의 모든 숫자 쌍을 검사해 보면 최대공약수가 항상 1이기 때문입니다.

접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

크기가 100이고 0으로 초기화된 배열 fac을 정의한다.
크기가 100이고 0으로 초기화된 배열 checkPrime을 정의한다.
gcdVal := 0
i := 0부터 i < n까지 반복하며(i는 1씩 증가):
    gcdVal := gcd(nums[i], gcdVal)
    fac[nums[i]] 값을 1 증가
만약 gcdVal이 1과 같다면:
    pw := true
    k := 2부터 k < 100까지 반복하며(k는 1씩 증가):
        checkPrime[k]가 참이면 다음 반복으로 건너뛴다
        c := 0
        j := k부터 j < 100까지 j := j + k씩 증가하며:
            c := c + fac[j]
            checkPrime[j] := true
        c <= 1이면 pw는 true를 유지
    pw가 참이면:
        "The numbers are pairwise coprime" 출력
    그렇지 않으면:
        "The numbers are setwise coprime" 출력
그렇지 않으면:
    "The numbers are not coprime" 출력

동작 원리

이 알고리즘은 크게 두 단계로 동작합니다. 먼저 배열의 모든 숫자에 대한 최대공약수를 누적으로 계산하여, 그 값이 1이 아니면 즉시 "서로소가 아님"을 판정합니다. 최대공약수가 1이라면, 각 소수 k에 대해 k의 배수(2k, 3k, ...)에 해당하는 숫자가 배열에 몇 번 등장했는지 세어 봅니다. 특정 소수의 배수가 두 개 이상 존재하면 그 두 수의 최대공약수는 k 이상이 되므로 쌍별 서로소가 될 수 없습니다. 따라서 모든 소수에 대해 배수가 최대 한 번씩만 등장하면 쌍별 서로소이고, 전체 최대공약수는 1이지만 일부 소수의 배수가 겹친다면 집합별 서로소로 판정됩니다.

C++ 구현 예제

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

void solve(int n, int nums[]){
   int fac[100] = {0};
   bool checkPrime[100] = {0};
   int gcdVal = 0;
   for(int i = 0; i < n ; i++) {
      gcdVal = __gcd(nums[i], gcdVal); 
      ++fac[nums[i]];
   }
   if(gcdVal == 1) {
      bool pw = true;
      for(int k = 2; k < 100; ++k) { 
         if(checkPrime[k])
          continue;
         int c = 0;
         for(int j = k; j < 100; j += k) {
            c += fac[j];
            checkPrime[j] = true;
         }
         pw = pw && c <= 1;
      }
      if(pw)
         cout<< "The numbers are pairwise coprime";
      else
         cout<< "The numbers are setwise coprime";
   }
   else
      cout << "The numbers are not coprime";
}
int main() {
   int n = 4, nums[] = {7, 11, 13, 17};
   solve(n, nums);
   return 0;
}

입력

4, {7, 11, 13, 17};

출력

The numbers are pairwise coprime