[백준][C++] 2960 에라토스테네스의 체

2960. 에라토스테네스의 체

2960번: 에라토스테네스의 체

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

기대하고 고대하던 에라토스테네스의 체를 이용해서 푸는 문제!!

 

1학년 때 엄청 어려워하면서 풀었던 기억이 있었는데, 알고리즘이 자세히 설명되어있어서 간단하게 풀 수 있는 문제였다. 아무리 간단한 문제라고 해도, 처음에 소수만 체로 거를 생각을 한 에라토스테네스가 천재 같다...

 

신기해서 코드가 돌아가는 흐름을 담은 동영상을 가져와봤다.

 

배수들을 제거해서 소수를 얻는 소거법이라니... 에라토스테네스는 천재인 것 같다.

 

 

 

지문에 나와있는대로 구현해봤다.

 

2부터 N까지 반복문을 돌려주었으며, 그 배수들을 체크해주었다. 체크한 숫자를 check 배열로 확인을 해주었다.

 

for (int i = 2; i <= n; i++)
{
    // 이미 체크한 숫자면 continue
    if (check[i]) continue;

    int p = i;

    while (p <= n)
    {
        // 이미 체크한 숫자면 체크하지 않는다
        if (!check[p])
        {
            check[p] = true;

            // K번째 지울 수일 때
            if (--k == 0)
            {
                cout << p << endl;
                return 0;
            }
        }

        // p의 배수를 순서대로 (ex) 3, 6, 9...)
        p += i;
    }
}

작년과 비슷하게 구현한 것 같다. 비록 구현 방법이 문제에 다 나와있지만, 작년보다 크게 성장한 것 같아서 기분이 좋다.

꾸준히 알고리즘 문제를 풀어나가서 지금 푸는 문제 정도는 눈 감고도 간단히 풀 수 있을 실력이 되고 싶다. 파이팅!