[백준 2960] 에라토스테네스의 체 (C#, C++) - soo:bak

문제 링크

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

설명

이 문제는 소수를 찾기 위해 사용하는 에라토스테네스의 체 알고리듬을 구현하면서,
그 과정에서 K번째로 지워지는 수를 구하는 시뮬레이션 문제입니다.

---

접근법

• 2부터 N까지 순서대로 지워나가며, 소수가 아닌 수들을 지울 때마다 카운트를 올립니다.
• 각 수 i가 아직 지워지지 않았고, i의 배수들을 순서대로 지울 때 K번째가 되면 해당 값을 출력합니다.
• 에라토스테네스의 체는 일반적으로 소수를 남기는 과정이지만, 이 문제에서는 지우는 순서를 추적해야 합니다.

---

Code

[ C# ]

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var input = Console.ReadLine()!.Split();
      int n = int.Parse(input[0]);
      int k = int.Parse(input[1]);

      var sieve = new bool[n + 1];
      int cnt = 0;

      for (int i = 2; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
          if (!sieve[j]) {
            sieve[j] = true;
            cnt++;
            if (cnt == k) {
              Console.WriteLine(j);
              return;
            }
          }
        }
      }
    }
  }
}

[ C++ ]

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, k; cin >> n >> k;
  int* sieve = new int[n + 1];
  fill_n(sieve, n, 0);

  int cnt = 0;
  for (int i = 2; i <= n; i++) {
    for (int j = 2; j <= n; j++) {
      if (!sieve[j] && j % i == 0) {
        sieve[j] = 1;
        cnt++;
        if (cnt == k) cout << j << "\n";
      }
    }
  }

  return 0;
}