C++ 백준 BOJ 2960 에라토스테네스의 체

 

에라토스테네스의 체는 소수를 찾는 유명한 알고리즘입니다.

 

 

 

에라토스테네스의 체

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

 

 

아주 큰 범위에서 소수를 판별하는 문제는 코딩테스트에서도 자주 나오는 문제인데

이때 사용하는 알고리즘입니다.

 

 

1929번 소수 구하기 문제를 풀기 전 먼저 알아야 합니다.

 

 

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

 

#include <iostream>
using namespace std;
bool arr[1001];

int main() {
	int N, K, val = 0, count = 0; //count 는 k번째 수를 판별
	for (int i = 0; i < 1001; i++) {//배열모두 true로 초기화 후 조건에 맞게 false로 지워줌
		arr[i] = true;
	}
	cin >> N >> K;
	for (int i = 2; i <= N; i++) {
		if (arr[i] == false) continue;
		for (int j = 1; i * j <= N && K != count; j++) {
			if (arr[i * j] == false)  continue;
			arr[i * j] = false;
			val = i * j;
			count++;
		}
		if (K == count) {
			cout << val;
			break;
		}
	}
	return 0;
}