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

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

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

 

코드

#include<iostream>

using namespace std;

int main(){
  int arr[1002];
  int N, K, res, count = 0, del = 2;
  cin >> N >> K;

  for(int i = 0; i < N; i++){
    arr[i + 1] = i + 1;
  }

  while(count != K){
    for(int i = 1; i*del <= N; i++){
      if(arr[del * i] != 0){
        if(count + 1 == K){
          res = arr[del * i];
          count++;
          break;
        }
        arr[del * i] = 0;
        count++;
      }
    }
    del++;
  }
  cout << res;
  return 0;
}

N개의 수가 있을 때 K번째 지워지는 수를 찾는 문제

2의 배수가 먼저 지워지고 그 다음은 3의 배수가, 다음은 5의 배수가 지워지는(4의 배수는 존재하지 않는다) 형식이다. 

배열의 요소가 0이면 지워진 것으로 인식하며 지울 때 마다 증가하는 count를 판별해 결과를 출력한다.