[java] 백준 알고리즘 4948번 베르트랑 공준 풀이

소수를 구할 때, '특정한 수를 나눌 경우 나누는 수가 특정한 수의 제곱근을 넘지 않는다'를 이용했다.

n<계산할 숫자들<=2n일 경우, 범위는 n이다. 

예를 들면, 10<계산할 숫자들<=20이면 총 10개의 숫자가 들어있다.

이때 소수가 아닌 수가 발견될 때마다 -1씩 해주면

최종적으로 소수가 n과 2n 사이에 몇 개 있는지 알 수 있다. 

* 풀이 소스 

 
public class Baekjoon4948{
 
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        int input = Integer.parseInt(st.nextToken());
        List<Integer> inputList = new ArrayList<>();
        inputList.add(input);
        
        while(input != 0) {
            st = new StringTokenizer(br.readLine());
            input = Integer.parseInt(st.nextToken());
            inputList.add(input);
        }
        
        for(int i=0; i<inputList.size()-1; i++) {
            int primeNumCount = inputList.get(i); // 범위 내의 숫자 갯수
            int startNum = inputList.get(i);
            
            for(int j=startNum+1; j<=2*inputList.get(i); j++) {
                double root = Math.sqrt(j);
                int divide = 2;
                if(j == 1) {
                    primeNumCount--;
                }
                while(divide<= root) { // 제곱근을 넘지 않는다.
                    
                    if(j%divide == 0) { // 소수가 아닐 때
                        primeNumCount--; // 범위 내의 숫자 갯수를 하나씩 
                        break;
                    }
                    divide++;
                }
                
            }
            bw.write(String.valueOf(primeNumCount));
            bw.newLine();
            bw.flush();
        }
        
        
    }
 
}