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

C++로 배열 내 모든 소수의 XOR 값 구하는 방법

문제 개요

이 문제에서는 n개의 요소로 구성된 배열이 주어지며, 배열에 포함된 모든 소수(Prime Number)의 XOR 값을 계산하여 출력하는 것이 목표입니다.

예시를 통해 문제를 살펴보겠습니다.

입력 − {2, 6, 8, 9, 11}

출력 − 9

설명 − 배열에서 소수는 2와 11뿐입니다. 따라서 2 XOR 11 = 9가 최종 결과가 됩니다.

해결 접근 방법

이 문제를 해결하려면 먼저 배열에서 모든 소수를 찾아낸 뒤, 찾은 소수들을 차례대로 XOR 연산하여 결과를 도출해야 합니다.

각 요소가 소수인지 판별하기 위해 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용합니다. 에라토스테네스의 체는 주어진 범위까지의 모든 소수를 O(n log log n)의 시간 복잡도로 효율적으로 찾을 수 있는 고전적인 알고리즘입니다.

전체 알고리즘의 동작 과정은 다음과 같습니다.

  1. 에라토스테네스의 체를 사용하여 필요한 범위까지의 소수 여부를 미리 계산합니다.
  2. 배열의 각 요소를 순회하면서 해당 요소가 소수인지 확인합니다.
  3. 소수라면 결과 변수에 XOR 연산을 누적합니다.
  4. 모든 요소에 대한 처리가 끝나면 최종 XOR 값을 반환합니다.

구현 예제

다음은 위 해결 방법을 C++로 구현한 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;
bool prime[100005];
void SieveOfEratosthenes(int n) {
   memset(prime, true, sizeof(prime));
   prime[1] = false;
   for (int p = 2; p * p <= n; p++) {
      if (prime[p]) {
         for (int i = p * 2; i <= n; i += p)
            prime[i] = false;
      }
   }
}
int findXorOfPrimes(int arr[], int n){
   SieveOfEratosthenes(100005);
   int result = 0;
   for (int i = 0; i < n; i++) {
      if (prime[arr[i]])
         result = result ^ arr[i];
   }
   return result;
}
int main() {
   int arr[] = { 4, 3, 2, 6, 100, 17 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"배열의 모든 소수의 XOR 값 : "<<findXorOfPrimes(arr, n);
   return 0;
}

실행 결과

배열의 모든 소수의 XOR 값 : 16

결과 분석 − 위 코드에서 배열 {4, 3, 2, 6, 100, 17} 중 소수는 3, 2, 17입니다. 3 XOR 2 = 1이고, 1 XOR 17 = 16이므로 최종 결과값은 16이 됩니다.

마무리

이처럼 에라토스테네스의 체를 활용하면 소수 판별을 사전에 처리할 수 있어, 배열 전체를 한 번만 순회하면서도 빠르게 답을 구할 수 있습니다. 배열의 크기가 커질 때 특히 유용한 접근 방식이므로, 코딩 테스트나 알고리즘 문제 풀이에서 자주 활용되니 꼭 익혀두시기 바랍니다.