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

에라토스테네스의 체

위 문제는 에라토스테네스의 체를 이용해서 소수를 찾는 알고리즘은 아님

그냥 에라토스테네스의 체 알고리즘의 매커니즘을 이용해서 푸는 문제라고 볼 수 있음

 

int N, K;
bool a[10000];
vector<int> v;

void PrimeNumber()
{
	for (int i = 2; i <= N; i++)
		a[i] = true;

	for (int i = 2; i <= N; i++)
	{
		if (a[i] == false) continue;
		for (int j = i; j <= N; j += i)
		{
			if (a[j] == false) continue;
			a[j] = false;
			v.push_back(j);
		}
	}

	if (v.size() >= K) cout << v[K - 1];

}

 

1. 2의 배수 삭제 -> 3의 배수 삭제 -> ( 중복되는건 건너뛰기 ) -> 4의 배수 삭제... ............

-> N의 배수 삭제..

 

2. 삭제할 때마다 vector에 넣기

 

3. vector에 K번째에 위치한 수 출력

 

끝!