[백준 2960] 에라토스테네스의 체 (C++/Python)

C++)

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

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

	int n, k;
	cin >> n >> k;

	vector<bool> v(n+1);
	fill(v.begin(), v.end(), false);

	int cnt = 0;
	for (int i = 2; i <= n; i++) {
		for (int j = i; j <= n; j += i) {
			if (!v[j]) {
				v[j] = true;
				cnt++;

				if (cnt == k) {
					cout << j;
					break;
				}
			}
		}
	}

	return 0;
}

 

 

 

Python)

import sys

n, k = map(int, sys.stdin.readline().rstrip().split())

arr = [False] * (n+1)

cnt = 0
for i in range(2, n+1):
    for j in range(i, n+1, i):
        if not arr[j]:
            arr[j] = True
            cnt += 1

            if cnt == k:
                print(j)
                break