[백준 / C언어] Day40. 소수 구하기 (1929)

2024. 07. 13 - 코딩테스트 스터디 Day40

 

 

01. 문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

 

02. 입력

첫째 줄에 자연수 M과 N이 빈칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

 

03. 출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

 

04-1. 예제 입력 1

3 16

 

 

04-2. 예제 출력 1

3
5
7
11
13

 

 

05. 풀이 및 답

소수는 1과 자기 자신 외의 수로는 나누어 떨어지지 않는 1보다 큰 정수이다.

 

#include <stdio.h>

int main() {
    int n, m;
    scanf("%d %d", &m, &n);
    
    for (int i = m; i <= n; i++) {
        if (i < 2) continue;
        int is_prime = 1;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                is_prime = 0; 
                break;
            }
        }
        if (is_prime == 1) printf("%d\n", i);
    }
    
    return 0;
}

i가 m일 때부터 n이 될 때까지 반복문을 돌면서, m부터 n까지의 모든 정수에 대해 소수 여부를 검사한다.

2보다 작은 수는 소수가 아니기 때문에 넘겨준다.

 

is_prime은 소수 여부를 나타내는 변수이며, 디폴트 값은 1이고 만약 소수가 아니라면 0 값을 가지게 된다.

 

j가 2부터 √i가 될 때까지 반복문을 돈다. i의 제곱근까지의 모든 수에 대해 i가 나누어 떨어지는지 검사하는 것이다.

(정수 n이 가질 수 있는 가장 큰 약수는 √n이기 때문이다)

 

이 과정에서 i를 0으로 나누어 떨어지게 하는 수가 있다면 is_prime을 0으로 설정하고 해당 반복문을 빠져나간다.

해당 반복문을 빠져나간 이후 is_prime이 1이면 i는 소수이므로 출력한다.

 

 

정답!

 

---

끝!