[C++][백준][알고리즘] 최대공약수, 최소공배수, 소수 🎯

최대 공약수는 Greatest Common Divisor으로 GCD라고 씁니다.
최소 공배수는 Least Common Multiple으로 LCM으로 씁니다.

 

2609번

2609번: 최대공약수와 최소공배수

#include <iostream>

/*
    [최대 공약수]
    유클리드 호제법 알고리즘
    
    1. 작은 수로 큰 수를 나눕니다.
    2. 나머지가 0이 될 때까지 계속 나눕니다.
    3. 나머지가 0이 되면, 해당 나누는 수가 두 수의 최대공약수가 됩니다.
    
    // 입력: 18, 24
    먼저 24를 18로 나눕니다.
    24 ÷ 18 = 1 ... 6
    나머지가 0이 아니므로, 이제 18을 나머지로, 6을 나눕니다.
    18 ÷ 6 = 3 ... 0
    나머지가 0이 되었으므로, 이 때의 나누는 수인 6이 18과 24의 최대공약수입니다. 따라서 최대공약수(GCD)는 6입니다.
*/

/*
    [최소 공배수]
    두 수의 곱을 그들의 최대공약수로 나누는 것으로 구할 수 있습니다.
    
    // 입력: 18, 24
    18과 24의 최대공약수는 6입니다.
    18 * 24 / 6은 72입니다.
*/

int gcd(int x, int y)
{
    if(y == 0)
        return x;
    else return gcd(y, x % y);
}

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    
    int g = gcd(a, b);
    
    printf("%d\n%d", g, a * b / g);

    return 0;
}

 

최대 공약수는 다음과 같이 계산합니다.

• 작은 수로 큰 수를 나눕니다.
• 나머지가 0이 될 때까지 계속 나눕니다.
• 나머지가 0이 되면, 해당 나누는 수가 두 수의 최대공약수가 됩니다.

최소 공배수는 다음과 같이 계산합니다.

• 두 수의 곱을 그들의 최대공약수로 나누는 것으로 구할 수 있습니다.

 

1978번

1978번: 소수 찾기

#include <iostream>
#include <cmath>

int main() {
    int N, input;
    int answer = 0;
    scanf("%d", &N);

    for(int i = 0; i < N; ++i)
    {
        scanf("%d", &input);    
        bool isPrime = true;
        
        for(int i = 2; i <= sqrt(input); ++i)
            if( input % i == 0)
            {
                
                isPrime = false;
                break;
            }   
        
        if(input != 1 && isPrime)
            ++answer;
    }

    printf("%d", answer);

    return 0;
}

• 최대 100개의 테스트 케이스가 소수인지 검사하여 소수의 개수를 리턴합니다.
• 약수의 성질을 활용하여 sqrt(input)까지 검사하여 i로 나누어 떨어지지 않는다면 소수로 볼 수 있습니다.
• 에라토스테네스의 체를 활용하여 매우 큰 범위의 소수를 더욱 빠르게 구할 수 있습니다.

[C++] 소수의 개수 (에라토스테네스의 체)

 

9020번

9020번: 골드바흐의 추측

#include <iostream>
#include <vector>
using namespace std;

vector<bool> isPrime(10001, true);

int main() {
    // 에라토스테네스의 체
    isPrime[0] = isPrime[1] = false;
    for(int i = 2; i < 10001; ++i)
        if(isPrime[i])
            for(int j = i * 2; j <= 10001; j += i)
                isPrime[j] = false;
            
    int T, n;
    scanf("%d", &T);
    for(int i = 0; i < T; ++i)
    {
        scanf("%d", &n);
        
        // 중간부터 시작하기
        int left = n / 2;
        while(true)
        {
            // 에라토스테네스의 체 배열에서 left, right가 모두 소수라면?
            if(isPrime[left] && isPrime[n - left])
            {
                // 출력 후 종료
                printf("%d %d\n", left, n - left);
                break;
            }
    
            --left;
        }
    }
    
    return 0;
}

• 에라토스테네스의 체를 기반으로 소수를 효울적으로 찾은 후 테스트케이스에 접근합니다.
• 각 테스트케이스의 입력에서 중간값부터 시작하여 left, right의 값이 모두 소수인지 확인하여 소수라면, 정답을 출력하고 마무리합니다.