[Java] 백준 - 4948번 : 베르트랑 공준 (Silver III)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	O
본인의 실력으로 풀었는가?	O

 

4948번: 베르트랑 공준

 

 

 

 

 

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
		//임의의 자연수를 받기 위한 변수		
		int num;

		//시간복잡도를 잡기 위해서 이미 확인한 숫자들은 소수인지 아닌지 boolean으로 구분하며 해시맵에 담아둠
		HashMap<Integer, Boolean> map = new HashMap<>();
		
		//숫자를 받아오면서 바로 num에 담고, 담은 숫자가 0일 때까지 반복
		while ((num = Integer.parseInt(br.readLine())) != 0) {

			//출력용 숫자를 모을 변수
			int result = 0;
			
			//임의의 자연수 n보다 크고, 2n보다 작거나 같아야 하기 때문에 범위는 n+1 ~ 2n까지임
			for (int i = num + 1; i <= 2 * num; i++) {
				//만약 map에 숫자가 없으면
				if (map.getOrDefault(i, null) == null) {
				  //소수인지 파악하기
					boolean check = true;
					for (int j = 2; j <= Math.sqrt(i); j++) {
						if (i % j == 0) {
							check = false;
							break;
						}
					}
					//check가 true이면 소수, false이면 소수가 아닌 숫자
				  //그대로 map에 넣고, result 값도 추가
					map.put(i, check);
					result += check ? 1 : 0;
				} else { //만약 map에 있으면 map의 boolean에 따라 result 값 추가
					result += map.get(i) ? 1 : 0;
				}
			}		
			bw.write(result + "\n");
		}
		
		bw.flush();
		bw.close();
	}
}

 

문제	결과	메모리	시간	코드 길이
4948	맞았습니다!!	218672 KB	648 ms	835 B