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

2960번: 에라토스테네스의 체 (acmicpc.net)

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

---

난이도 : 실버 4

 

생각보다 오래 걸렸던 문제였어요 ㅠ

에라토스테네스의 체를 공부하고 관련된 코드를 보면서 짜다가

보통의 에라토스테네스 알고리즘 코드랑 이 문제가 약간 다르잖아요? P를 포함해가지고 제거되는 거라..

하튼간 쉽지 않았던 문제!! 였습니다. 저한테는...

 

풀이과정 :

 

1. visited배열에 2부터 N까지 집어넣는다! (v(2) =2, v(3)=3 ... 이런식으로)

2. i가 2일때는 2, 4, 6, 8....  3일때는 3,6,9,... 이런식으로 지워져야 하기때문에 이중 for문을 이용하여

j가 i의 배수가 되도록 하게 합니다!! (코드보시면 이해가용)

3. k번째 지워지는 수를 알아야 하므로 카운트할 cnt 변수 선언!(미리선언해놓음)

4. 이중 for문을 돌면서 cnt에 1씩 더해줍니다.

5. 중복을 방지하기위해 이미 센 숫자는 0으로 바꿈

6. 그래서 만약에 visited[j] =0이면 continue 해서 세지 않도록 함!

 

 

답 :

#include <iostream>
#include <algorithm>


int prime(int n,int k) {
	int visited[1001] = { 0 };
	int cnt = 0;
	for (int i = 2; i <= n; i++) {
		visited[i] = i; 
	}
	for (int i = 2; i <= n; i++) {
		for (int j = i; j <= n; j += i) {
			if (visited[j] == 0) continue; //이미 센 숫자는 0이되어 반복문이 돌지 않게함
			cnt++;
			if (cnt == k) {
				return visited[j];
			}
			visited[j] = 0;
		}
		
	}

}


int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	printf("%d",prime(n, k));
}