https://github.com/ljmyung1224

활동 기록

7/12

1929번 - 소수 구하기: 처음에는 약수가 2개이면 출력하는 방식에서 수정

#include<stdio.h>
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    for(int i=n;i<=m;i++)
    {
        if(i==1) i++;
        int c=1;
        for(int j=2;j*j<=i;j++) // j*j가 핵심 (j<=sqrt(i)와 동일)
        {
            if(i%j==0)
            {
                c=0;
                break;
            }
        }
        if(c==1) printf("%d\\n", i);
    }
}

어떤 수의 약수는 항상 √n 이하인 수 중에 하나가 존재하므로, j * j <= n 조건으로 소수 판별을 최적화할 수 있다. (시간초과 방지)

4948번 - 베르트랑 공준: 소수 구하기 문제의 로직과 동일,

에라토스테네스의 채로도 풀이 가능(더 빠름)

• 처음에 n부터 2n까지 다 소수라고 가정
• 그 다음, 2를 제외한 2의 배수, 3을 제외한 3의 배수… 식으로 하나하나 소수가 아닌 애들만 걸러냄
• 이렇게 걸러지고 남은 수는 진짜 소수

2609번 - 최대공약수와 최소공배수: 유클리드 호제법 사용

int a, b, x, y, temp;

scanf("%d %d", &a, &b);
x = a;
y = b;

while (y != 0) // 유클리드 호제법 
{
	temp = x % y;
	x = y;
	y = temp;
}

printf("최대공약수(GCD): %d\\n", x);
printf("최소공배수(LCM): %d\\n", a*b/x);

a = 48, b = 18

• temp = 48 % 18 = 12
• x = 18
• y = 1