[백준] 4948번 : 베르트랑 공준 _ JAVA ( 주석 설명 )

1번

→ 제곱근을 이용한 범위 내의 소수 개수 파악

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {

    //전체 시간복잡도 : O(sqrt(N))
    //전체 공간복잡도 : 자료구조 x
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder(); //출력값을 한번에 출력하기 위한 변수이다.

        while(true) {
            int num = Integer.parseInt(br.readLine()); //n< <=2n 범위 내의 소수 개수를 구하기 위한 입력을 받는다.
            if(num==0) //0을 입력받으면 종료
                break;

            int count = 0; //테스트케이스마다 카운트를 다르게 해주어야 한다.

            for(int i=num+1;i<=num*2;++i){ //범위 내의 소수를 구하기 위한 반복이다.
                boolean judge = true; //소수임을 판단하기 위한 boolean 변수이다. //기본값을 true 로 설정 -> 2는 소수

                for(int j=2;j<=Math.sqrt(i);++j){ //sqrt(i) 이후의 계산은 나누어 떨어지지 않거나, 나누어 떨어질 경우 이 전에 이미 구할 수 있으므로 계산이 무의미하다.
                    if(i%j==0){ //나누어 떨어질 경우(=1과 자기 자신을 제외한 약수가 있을 경우)
                        judge = false; //소수가 아니다.
                        break;
                    }
                }
                if(judge) //소수일 경우 카운트
                    count++;
            }
            sb.append(count).append('\n'); //범위 내의 소수 개수를 sb 변수에 더한다.
        }

        System.out.println(sb); //각 테스트케이스에 대한 범위 내 소수의 개수 출력
    }
}

 

---

 

2번

→ '에라토스테네스의 채'를 이용한 범위 내의 소수 개수 파악

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
    static boolean[] prime = new boolean[123456*2+1]; //소수 : false, 합성수 : true

    //전체 시간복잡도 : O(log(log(N))
    //전체 공간복잡도 : O(N)
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder(); //출력값을 한번에 출력하기 위한 변수이다.

        prime[1] = true; //1은 소수가 아니다.

        //num 을 두 수의 곱으로 표현한 순서쌍은
        //sqrt(num)*sqrt(num)을 기준으로 대칭을 이루고 있으므로,
        //그 이후의 값은 계산할 필요가 없다.
        for(int i=2;i<=Math.sqrt(prime.length);++i){
            for(int j=i*i;j<= prime.length;j+=i){ //i*2는 i==2일 때 모두 true 처리가 되므로, 약간의 효율을 더하기 위해 i*i을 사용한다.
                prime[j] = true;
            }
        }

        while(true) {
            int num = Integer.parseInt(br.readLine()); //n< <=2n 범위 내의 소수 개수를 구하기 위한 입력을 받는다.
            if(num==0) //0을 입력받으면 종료
                break;

            int count = 0; //테스트케이스마다 카운트를 다르게 해주어야 한다.

            for(int i=num+1;i<=num*2;++i) { //범위 내의 소수를 구하기 위한 반복이다.
                if(!prime[i])
                    ++count;
            }

            sb.append(count).append('\n'); //범위 내의 소수 개수를 sb 변수에 더한다.
        }

        System.out.println(sb); //각 테스트케이스에 대한 범위 내 소수의 개수 출력
    }
}