백준 2960번 에라토스테네스의 체

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

기존에 구현을 한 에라토스테네스의 체 코드에서 살짝 변형만 시키면 쉽게 AC를 받을 수 있는 코드였습니다.

기존의 에라토스테네스의 체 코드는 소수를 찾는 것이 목적이였다면 이번 문제는 해당 숫자가 몇 번째로 지워지는지를 찾기 때문에 반복문에서 종결 조건을 i * i <= MAX 가 아닌 i * i <= MAX * MAX로 해줘야했습니다.

#include <iostream>

using namespace std;

 

const int MAX = 1000 + 1;

 

int N, K;

bool minFactor[MAX]; //minFactor[i] -> i의 가장 작은 소인수(i가 소수인 경우 자기 자신)

 

//에라토스테네스의 체

int eratosthenes(int cnt)

{

        for (int i = 2; i <= N; i++)

                 minFactor[i] = true;

 

        //에라토스테네스의 체 수행

        for (int i = 2; i * i <= MAX * MAX; i++)

        {

                 if (minFactor[i])

                 {

                         minFactor[i] = false;

                         cnt--;

                         if (cnt == 0)

                                 return i;

 

                         for (int j = i * i; j <= N; j += i)

                                 if (minFactor[j])

                                 {

                                          minFactor[j] = false;

                                          cnt--;

                                          if (cnt == 0)

                                                  return j;

                                 }

                 }

        }

}

 

int main(void)

{

        cin >> N >> K;

 

        cout << eratosthenes(K) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~