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

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

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

---

⭐ 내 소스 코드

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, k,count=0, result;
	vector<int> vec;

	cin >> n >> k;

	for (int i = 1; i <= n; i++) {
		vec.push_back(i);
	}
	
	for (int i = 2; i <= n; i++) {
		for (int j = 1; i*j <= n; j++) {
			if (vec[i*j - 1] != 0) {
				vec[i*j - 1] = 0;
				count++;
				if (count == k) {
					result = i * j;
					break;
				}
			}
		}
		if (count == k) {
			break;
		}
	}
	cout << result;
	return 0;
}

✨ 문제 풀이 결과

🙏 문제 풀이

• i는 2부터 시작하여 배로 증가시킬 수를 지정한다
• j는 차근차근 증가시켜 i*j의 값을 차례대로 구해나간다
• j*i의 값이 지워지게 되면 해당 값이 있는 인덱스(j*i-1)의 값을 0으로 바꾸어준다
• 숫자를 지웠으니 count값을 증가시켜주고, 해당 값이 우리가 찾고자 하는 k와 같은지 확인한다