백준 1929번 - 소수 구하기 C++

문제

알고리즘 분류 : 에라토스테네스의 체

 

해결 방법 : 에라토스테네스의 채를 구현하면 끝나는 문제.

 

아쉬웠던 점

글을 쓰며 생각이 들었는데, Num 배열 또한 절반만 사용할 수 있었는데 그러지 않아서 아쉽다.

 

코드

#include <iostream>
using namespace std;
 
bool Num[1000001] = {};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int Start, End;
    cin >> Start >> End;
 
    for (int i = 3; i <= End; i += 2)
        if(!Num[i])
            for (int j = 3; j*i <= End; ++j)
                    Num[i * j] = true;
    
    if (Start == 1 || Start == 2)
    {
        Start = 3;
        if (End != 1)
            cout << "2" << '\n';
    }
    else if (Start % 2 == 0)
        ++Start;
 
    for (int i = Start; i <= End; i += 2)
        if (!Num[i])
            cout << i << '\n';
}

핵심은 반복문을 2개씩 증가하면서 진행하였다. (어쩌피 2의 배수는 무조건 소수가 아니니까 2는 번외로 생각했음.) 이를 위하여 20번~27번째 줄에 2를 출력하기 위해서 뻘짓이 살짝 들어갔지만, 더 이득이라고 생각한다.