백준 문제 풀이 - 소수 구하기 1929번

📜 문제 이해하기

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

💡 문제 재정의

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

✏️ 계획 수립

이번 문제의 핵심은 최대한 짧은 시간안에 소수를 구하는 것이다. 여러 방법을 써봤지만 에라토스테네스의 체를 사용하는 것이 가장 방법이 빨랐다.

💻 계획 수행

#include <iostream>
using namespace std;

int sieve[1000001] = {0, 1};

int main() {
    int M, N;
    cin >> M >> N;

    for (int i = 2; i <= N; i++)
        for (int j = 2; i * j <= N; j++)
            sieve[i * j] = 1;

    for (int i = M; i <= N; i++)
        if(!sieve[i]) cout << i << '\n';

    return 0;
}

🤔 회고

처음에는 이보다 효율적으로 짤 수 없다고 생각했는데 자꾸 시간 초과가 발생했다. 이유를 찾아보니 endl이 시간초과의 주범이었다. 따라서 '\n'을 쓰는게 정신건강에 좋을것같다.