[C]백준 Q.2609,1978,1929 최대공약수 ~ 소수 문제

원래는 기초 수학 문제부분을 그냥 한번다 다 끝내고 글하나로 쓰자생각에 미뤄뒀다가

6588번 골든바흐 문제풀다 냅둬버려서 이러다 또 상당히 글을 나중에 잊을쯤에 쓰겠구나 싶어서 그냥 바로 돌입

 

최대공약수와 최소공배수  https://www.acmicpc.net/problem/2609

아마 관련 전공수업을 들었던 사람이면 이름은 한번 들었을 그 유클리드 호재법 관련 문제

다 잊은 나도 이름은 기억하는 알고리즘인데

gcd(a,b)=gcd(b,r) 요게 핵심 사고 

설명을 쭉~ 나열할 정도로 원리를 꾀고 있는것도 아니라 그냥 써먹자 

사실 gcd는 c언어에는 모르겠지만 다른 언어의 수학라이브러리에선 종종 보였던거같다

뭐 그렇게 크기만 잡아주고 재귀돌려주면 짜잔 GCD함수 완성

최소공배수는 gcd나오면 나오면 항상 같이 나오는 세트템같은 녀석이라 

a * b를 ab의 최대공약수로 나눈값을 주면된다

그런데 타입의 오버플로우를 막기위해 먼저 a값을 먼저 나눠줘서 값을 낮춘다

// 최대공약수 유클리드 호제법
long calcGCD(long num1, long num2) {
    long a,b;
    
    if (num1 > num2) {
        a = num1;
        b = num2;
    } else {
        a = num2;
        b = num1;
    }
    
    if (b == 0) return a;
    return calcGCD(b, a % b);
}

// 최소공배수 gcd이용 버전
long calcLCM(long num1, long num2) {
    long a,b;
    
    if (num1 > num2) {
        a = num1;
        b = num2;
    } else {
        a = num2;
        b = num1;
    }
    
    return (a / calcGCD(a, b)) * b;
}
 

int main(int argc, const char * argv[]) {
    
    long num1,num2;
    
    while (scanf("%ld %ld", &num1, &num2) == 2) {
        long gcd = calcGCD(num1, num2);
        long lcm = calcLCM(num1,num2);
        printf("%ld\n%ld\n", gcd, lcm);
    }
    
    return 0;
}

 

소수 찾기 https://www.acmicpc.net/problem/1978

이전에 에라토스 뭐시기의 채 문제에서 했던 코드를 살짝 변경

int solution(int *values, int nSize) {
    int count = 0;

    for (int i = 0; i < nSize; i++) {
        int value = values[i];

        if (value == 1) continue;

        int isPrime = 1;
        for (int j = 2; j * j <= value; j++) {
            if (value % j == 0) {
                isPrime = 0;
                break;
            }
        }

        if (isPrime) count++;
    }

    return count;
}

 

소수 구하기  https://www.acmicpc.net/problem/1929

위의 소수 찾기 문제에 썻던 코드를 살짝 변형해서 쭉

void printPrime(int min, int max) {
    if (min < 2) min = 2;

    for (int i = min; i <= max; i++) {
        int isPrime = 1;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                isPrime = 0;
                break;
            }
        }
        
        if (isPrime) printf("%d\n", i);
    }
}

 

 

뭘 시도했었는지 잘 기억이 안나서 역시 문제는 풀자마자 글을 써야 이야기할 거리가 생길텐데 이런식으로 몰아서 쓰기는 안좋은거같다

 

아래는 깃허브 레포지토리

https://github.com/wiwi-git/c-baekjoon

GitHub - wiwi-git/c-baekjoon: 블로그 업데이트용 백준 코드

 

 

 

 

추신.

아 요즘은 중국장기겜에 대해 좀 코딩하고있다. 하고있는 게임에 나오는 중국장기문제를 좀 쉽게 풀고싶어서 게임을 찾았는데 이게 인겜은 해외유저를 위해 체스마냥 모양으로 되어있거에 반해 찾은게임은 중국한자라 문제 배치에 매번 뭔가 실수가 나서 이거 내가 모양만 바꾸자 했던게 뭔가 질질 끌고있다.

첫날에 진도가 많이 안나가니 의욕이 꺽여서 그런가 진행이 아예 멈춰버렸는데 

슬슬 다시 잡아서 완료시킨후 블로그에 올려볼 예정