[c/c++] 백준 1929 (Silver 3)

🔨 문제

https://www.acmicpc.net/problem/1929

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

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

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

🔨 해결방법

소수를 구할 때 시간에 문제가 생긴다면 너무 유명한(사실 처음 들어보는) '에라토스테네스의 체'를 이용하여 소수를 구하면 된다.

에라토스테네스의 체

이 알고리즘의 작동 원리는 제일 작은 소수인 2부터 시작하여 자기 자신 제외 2의 배수에 해당하는 값들을 max값(사용자 지정)까지 모두 지우고, 그 다음 지워지지 않은 수(3)부터 시작해서 그것의 배수만큼 또 지우는 것이다. 이 동작을 반복해서 max값까지 모두 지우는 것이다.

예를 들어, 15까지의 소수를 구하면 2 3 4 5 6 7 8 9 10 11 12 13 14 15

2의 배수 지우고
3의 배수 지우고
5의 배수 지우고
...

🔨 코드

#include <iostream>
using namespace std;

int main() {

    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    int arr[1000001] = { 0 };
    
    // 1. 배열 생성 후 초기화
    for (int i = 2; i <= m; i++) {
        arr[i] = i;
    }
    
    // 2. 2부터 시작하여 특정 수의 배수에 해당하는 수를 모두 지움
    for (int i = 2; i <= m; i++) {
        if (arr[i] == 0) continue;  // 이미 비워져 있으면 skip
        for (int j = i * 2; j <= m; j += i) {  // 비워져있지 않다면 그 숫자의 배수부터 출발하여 모두 비움
            arr[j] = 0;
        }
    }

    for (int i = n; i <= m; i++) {
        if (arr[i] != 0) cout << arr[i] << '\n';
    }

    return 0;
}