C++ 2960 에라토스테네스의 체 [구현]

 

 

 

 

- std::list로 값 관리

-> 2부터 N까지 모든 정수를 담는다.

 

- while

-> 가장 작은수는 list의 맨앞의 값 (P) 

-> P와 P의 개수값 제거해가며 K번째 지우는 수를 찾는다.

 

#include <iostream>
#include <list>

int main()
{
	std::list<int> nums;

	int N, K;

	std::cin >> N >> K;

	for (int i = 2; i <= N; i++)
	{
		nums.push_back(i);
	}

	int checkcount = 0;

	while (true)
	{
		int CalValue = nums.front();
		nums.pop_front();

		++checkcount;

		if (checkcount == K)
		{
			std::cout << CalValue<<"\n";
			break;
		}
		std::list<int>::iterator StartIter = nums.begin();
		std::list<int>::iterator EndIter = nums.end();

		for (; StartIter != EndIter; ++StartIter)
		{
			int deleteValue = *StartIter;

			if (deleteValue % CalValue == 0)
			{
				*StartIter = -1;

				++checkcount;
				if (checkcount == K)
				{
					std::cout << deleteValue << "\n";
					return 0;
				}
			}
		}

		while (true)
		{
			if (nums.front() != -1)
			{
				break;
			}

			nums.pop_front();
		}
	}

	return 0;
}