백준 2960번(에라토스테네스의 체)c++

 

문제

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

기존 에라토스테네스에서 응용 문제입니다. 

에라토스테네스는 소수를 제외하고 합성수를 지웠는데 여기 문제에서는 소수까지 지워서 

임의의 정수 k를 입력받아 k 번째 지운 수를 출력해주는 문제입니다.

 

int n, k;
cin >> n >> k;
    
int cnt = 0;
    
bool flag = false;

먼저 어디까지 소수를 판별할 n 과 몇번째에서 지우는지 k 를 입력 받습니다.

변수 cnt를 선언해줘서 숫자를 지울때마다 cnt가 올라가게 해서 cnt가 k가 되면 그 수를 출려하게끔하는 장치입니다.

bool형 flag는 cnt가 k로 되면 더이상 나머지 것을 볼 필요가 없으므로 flag를 true로 바꿔주어서 나중에 for문을 

탈출하게끔 하는 장치입니다.

for (int i = 2; i <= n; i++) {
		arr[i] = i; //인덱스에 자기자신 value 초기화
	}
	for (int i = 0; i <= n; i++) {
		if (arr[i] == 0) //value가 0이면 합성수이므로 continue
			continue;
		for (int j = i; j <= n; j += i) {
			if (arr[j] == 0) //합성수는 continue
				continue;
			cnt++; //지우게 되므로 cnt의 값을 늘려준다
			arr[j] = 0; // value값을 0으로 바꿔주어 지웠다는 표시를 해준다
			if (cnt == k) { //cnt가 k이면 
				cout << j; //그 수를 출력하고
				flag = true; //flag를 true로 바꿔주어
				break; //for문을 탈출한다
			}
		}
		if (flag) //cnt가 k이면 flag=true이므로 break를통해 빠져나간다. false면 못빠져나감
			break; 
}

최종 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int arr[1001];
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	int cnt = 0;
	bool flag = false;
	for (int i = 2; i <= n; i++) {
		arr[i] = i;
	}
	for (int i = 0; i <= n; i++) {
		if (arr[i] == 0)
			continue;
		for (int j = i; j <= n; j += i) {
			if (arr[j] == 0)
				continue;
			cnt++;
			arr[j] = 0;
			if (cnt == k) {
				cout << j;
				flag = true;
				break;
			}
		}
		if (flag)
			break;
	}
	return 0;
}