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

C++로 두 수의 공통 소인수 구하기: 에라토스테네스의 체와 GCD 활용법

두 개의 숫자 x와 y가 주어졌을 때, 두 수 사이의 공통 소인수를 찾아야 하는 문제입니다. 공통 소인수는 먼저 두 수의 공약수를 구한 뒤, 그중에서 소수에 해당하는 값만 골라내면 쉽게 찾을 수 있습니다.

여기서 핵심 아이디어는 두 수의 공통 소인수는 결국 두 수의 최대공약수(GCD)의 소인수와 같다는 점입니다. 따라서 GCD만 구하면 별도의 비교 과정 없이 효율적으로 답을 얻을 수 있습니다.

예제

입력 − x = 10, y = 20
출력 − 두 수의 공통 소인수: 2 5

설명 − 10과 20의 공통 소인수는 2와 5뿐입니다.

입력 − x = 34, y = 12
출력 − 두 수의 공통 소인수: 2

설명 − 34와 12의 공통 소인수는 2 하나뿐입니다.

알고리즘 접근 방식

  • 두 수 x와 y의 값을 입력받습니다.

  • 공통 소인수를 찾는 함수를 작성하고, 그 내부에서 다음 단계를 수행합니다.

  • x와 y의 최대공약수(GCD)를 저장할 변수를 선언합니다.

  • 2부터 GCD 이하까지 반복하는 루프를 만들고, 매 반복마다 i를 증가시킵니다.

  • 루프 안에서 prime[i]가 참이면서 동시에 GCD % i == 0(i가 GCD의 약수)인지 검사합니다.

  • 조건이 참이면 해당 값 i를 출력합니다.

  • 모든 반복이 끝나면 결과를 출력합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
#define MAX 100001
bool prime[MAX];

void SieveOfEratosthenes(){
    // "prime[0..n]" 불리언 배열을 생성하고 모든 값을 true로 초기화합니다.
    // prime[i]의 값은 i가 소수가 아니면 최종적으로 false가 됩니다.
    memset(prime, true, sizeof(prime));
    // 0과 1은 소수가 아닙니다.
    prime[0] = false;
    prime[1] = false;
    for (int p = 2; p * p <= MAX; p++){
        // prime[p]가 변경되지 않았다면 p는 소수입니다.
        if (prime[p] == true){
            // p의 모든 배수를 합성수로 표시합니다.
            for (int i = p * p; i <= MAX; i += p){
                prime[i] = false;
            }
        }
    }
}

// 두 수의 공통 소인수를 찾는 함수
void common_prime(int x, int y){
    // 주어진 두 수의 GCD(최대공약수)를 구합니다.
    int g = __gcd(x, y);
    // g의 소인수를 찾습니다.
    for (int i = 2; i <= (g); i++){
        // i가 소수이면서 g의 약수인 경우
        if (prime[i] && g % i == 0){
            cout << i << " ";
        }
    }
}

// 메인 코드
int main(){
    // 에라토스테네스의 체 생성
    SieveOfEratosthenes();
    int x = 20, y = 30;
    cout<<"Common prime factor of two numbers are: ";
    common_prime(x, y);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −

Common prime factor of two numbers are: 2 5

동작 원리 정리

이 알고리즘은 크게 두 단계로 나눌 수 있습니다. 첫 번째 단계는 에라토스테네스의 체(Sieve of Eratosthenes)를 이용해 미리 소수 여부를 판별해 두는 것입니다. 이렇게 하면 특정 숫자가 소수인지 확인할 때 O(1) 시간 만에 판단할 수 있어 전체 성능이 크게 향상됩니다.

두 번째 단계는 __gcd() 함수로 두 수의 최대공약수를 구한 뒤, 2부터 GCD까지의 숫자 중 소수이면서 GCD의 약수인 값을 모두 출력하는 것입니다. 전체 시간 복잡도는 체 생성에 O(MAX log log MAX), 소인수 탐색에 O(GCD)이며, 여러 쿼리를 처리해야 하는 상황에서도 효율적으로 동작합니다.