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

< 백준 2960번 에라토스테네스의 체 - 마포 코딩박 >

사용한 알고리즘: 에라토스테네스의 체


 문제 자체가 그 유명한 에라토스테네스의 체를 구현하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 11~24)
 첫 for 문으로 i=2~N까지의 모든 i를 봅니다.
 두번째 for 문으로 j=i 의 배수( i, 2i, 3i, ... )들을 차례로 보며 bool[j] = true 로 한번 본 수를 체크합니다. 이를 통해 한번 본 수는 다시는 보지 않습니다. ( 문제에서 ' 지운다 ' 는 것을 bool 배열을 만들어 구현했습니다. )
 또한 지우는 횟수를 저장하여 K번째 지우는 수를 답으로 출력합니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MAX = 2000;
	int N, K, cnt, ans;
	bool visited[MAX];
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> K;
	for(int i = 2; i<=N; ++i){
	if(ans) break;
	if(visited[i]) continue;
	for(int j = i; j<=N; j+=i){
	if(visited[j]) continue;
	cnt++;
	if(cnt==K){
	ans = j;
	break;
	}
	visited[j] = true;
	}
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 2960.cpp hosted with ❤ by GitHub