반응형
문제

에라스토테네스의 체
https://skylarcoding.tistory.com/361
문제 반례 찾는 법
아래 링크에서 확인할 수 있다.
https://skylarcoding.tistory.com/303
코드
package AlgorithmStudy.src.silver;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class S4948 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = 1;
while (n != 0) {
n = Integer.parseInt(br.readLine());
if (n != 0) {
isPrime(n);
}
}
}
public static void isPrime(int n) {
boolean[] list = new boolean[2 * n + 1];
int cnt = 0;
list[0] = true; // 소수 아님
list[1] = true;
for (int i = 2; i * i<= 2 * n; i++) {
if (!list[i]) {
for (int j = i * i; j <= 2 * n; j += i) {
list[j] = true;
}
}
}
for (int i = n + 1; i <= 2 * n; i++) {
if (!list[i]) {
cnt ++;
}
}
System.out.println(cnt);
}
}
해설
기본적인 에라스토테네스의 체 코드에 대한 설명은 아래 포스팅을 보면 된다.
https://skylarcoding.tistory.com/361
베르트랑 공준에서 좀 더 심화 설명으로 나아가자면, 입력받은 n 과 2n 사이의 소수를 구해야 하는게 추가적인 내용이다. for 문에서 마지막 숫자가 2 * n 값임을 변경해주면 된다.
기존에 소수일 경우 출력하던 값은 cnt 를 추가하여 소수일 경우 cnt 를 증가하여, 마지막에 cnt 값만 나오면 된다.
소수 구하기와 매우 유사한 문제이다.
반응형