백준 1929 : 소수 구하기

문제 링크입니다 https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

입력으로 주어지는 자연수 M과 N이 있을 때, M 이상 N 이하의 소수를 모두 출력하는 문제였습니다. 에라토스테네스의 체를 이용해 문제를 해결했습니다. 

 

 

[소스코드]

 

#include<cstdio>
int m, n;
 
// 인덱스에 해당하는 수가 소수이면 false
// 소수가 아니면 true가 들어있는 배열
bool check[1000001];
 
int main(void) {
    scanf("%d%d", &m, &n);
    check[1] = true;      // 1은 소수가 아닙니다
    if (n == 1) return 0; // n이 1이면 아무것도 출력하지 않고 종료
    
    // 2부터 n까지의 수 중 소수이면 해당 수의 배수들은 
    // 절대 소수가 아니므로 배수들을 true로 만들어줍니다
    for (int i = 2; i <= n; i++) {
        if (!check[i]) {
            for (int j = i * 2; j <= n; j += i)
                check[j] = true;
        }
    }
    // m 이상 n 이하의 모든 소수를 출력합니다
    for (int i = m; i <= n; i++)
        if (!check[i]) printf("%d\n", i);
    return 0;
}