알고리즘
[백준, 자바, 4948번] 베르트랑 공준
hminor
2024. 11. 13. 16:01
반응형
풀이
- 해당 문제는 특정 정수보다 크면서 2배한 것 보다 작거나 같은
- 모든 소수를 구하는 문제로서
- 입력값은 0이 나올 때까지 받기에
- 우선은 모든 입력 값을 배열에 담아두면서
- 가장 큰 값을 찾고, 이후에 큰 값의 2배에 해당 하는 배열을 만들어서
- 모든 소수를 에라토스테네스의 체를 활용하여 판별한 뒤
- 이후 배열을 돌려가며 범위에 해당하는 소수를 카운팅하여 해결.
import java.io.*;
import java.util.*;
public class _4948 {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
List<Integer> li = new ArrayList<>();
int mx = 0;
while (true) {
int N = sc.nextInt();
if (N==0) break;
li.add(N);
if (N>mx) mx = N;
}
boolean[] prime = new boolean[2*mx+1];
prime[1]=true;
for (int i=2; i<2*mx; i++) {
for (int j=i*2; j<=2*mx; j+=i) {
if (!prime[j]) prime[j]=true;
}
}
for (int num: li) {
int cnt = 0;
for (int i=num+1; i<=2*num; i++) {
if (!prime[i]) cnt++;
}
bw.write(cnt+"\n");
}
bw.flush();
}
}