[BOJ] 2960번 : 에라토스테네스의 체

1. problem : 

https://www.acmicpc.net/problem/2960

 

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n, k;
int board[1005]; 
vector<int> ans;
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;

	for (int i = 2; i <= n; i++) {
		if (board[i]) continue;
		for (int j = i; j <= n; j += i) {
			if (board[j]) continue; 
			board[j] = 1; 
			ans.push_back(j);
		}
	}
	cout << ans[k-1];
}

에라토스테네스의 체를  이용해 풀었다. 좀 더 효율적인 방법이 있을 것 같다. 

 

3. solution 2 :

// Authored by : jihwan0123
// Co-authored by : -
// http://boj.kr/c980507acdc34d5ea79e397129f664c5
#include <bits/stdc++.h>
using namespace std;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<bool> state(n+1, true);
  for (int i=2; i<=n; i++){
    if (!state[i]) continue;
    for (int j=i; j<=n; j+=i){
      if (!state[j]) continue;
      state[j] = false;
      k--;
      if (k == 0){
        cout << j;
        return 0;
      }
    }
  }
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x12/solutions/2960.cpp

basic-algo-lecture/0x12/solutions/2960.cpp at master · encrypted-def/basic-algo-lecture

벡터에 수를 저장하는 대신, k를 cnt로 이용해, 메모리를 효율적으로 사용한 코드다. 

 

4. solution 3 :

#include <bits/stdc++.h>
using namespace std;
int n, k;
int board[1005]; 
vector<int> ans;
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;

	for (int i = 2; i <= n; i++) {
		if (board[i]) continue;
		ans.push_back(i);
		for (int j = i * i; j <= n; j += i) {
			if (board[j]) continue; 
			board[j] = 1; 
			ans.push_back(j);
		}
	}
	cout << ans[k-1];
}