문제

에라토스테네스의 체

풀이

오래간만에 에라토스테네스의 체 문제 입니다. 구현해야 할 내용은 문제에서 모두 제시하고 있기 때문에 문제대로 구현해주면 됩니다

// 이미 지운 것인지 확인하는 에라토스테네스의 체
int[] arr = new int[n + 1];

// 지운 소수의 개수
int count = 0;

// 1. 2부터 N까지 모든 정수를 적는다.
for (int i = 2; i <= n; i++) {

// 2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
int index = arr[i];

// 3.P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
for (int j = i; j <= n; j += i) {
	if (arr[j] == 0) {
    	count++;
    }
    // 4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
    if (count == k) {
    	System.out.println(j);
        System.exit(0);
    }
}

전체 코드

전체 코드