[백준/BOJ] 백준 2960번 : 에라토스테네스의 체

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

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

규칙을 이용해 k번째 지워진 수를 구한다

 

코드

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

int n, k;
int check[1001];

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

	memset(check, 0, sizeof(check));

	int cnt = 0;

	cin >> n >> k;

	for (int i = 2; i <= n; i++)
	{
		if (check[i] == 0)
		{
			check[i] = 1;
			cnt++;

			//k번째 지워진 수 일때
			if (cnt == k)
			{
				cout << i;
				return 0;
			}
		}

		for (int j = i * 2; j <= n; j = j + i)
		{
			if (check[j] == 0)
			{
				check[j] = 1;
				cnt++;

				//k번째 지워진 수 일때
				if (cnt == k)
				{
					cout << j;
					return 0;
				}
			}
		}
	}

	return 0;
}