[백준] 4948번 : 베르트랑 공준 - Java

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

---

---

참고 유형

https://unknownomad.tistory.com/147

[백준] 1978번 : 소수 찾기 - Java

---

구현 방법

1. Scanner 로 입력받는 방법
2. BufferedReader 로 입력받는 방법
3. BufferedReader 로 입력받되 효율적으로 출력하는 방법
4. 3번과 같으나 소수의 개수를 미리 구해놓고 해결하는 방법

---

알고리즘

• 에라토스테네스의 체 활용

---

풀이

1. Scanner

import java.util.Scanner;

public class Main {
    /*
    n > 123456 ➡ 2n : 최대 246912
    배열 index : 0부터 시작 ➡ 246912 + 1
    */
    public static boolean[] prime = new boolean[246913];

    public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

        get_prime(); //소수 찾기

        while(true) {
            int n = in.nextInt();
            if(n == 0) {
                break;
            }

            int count = 0; //소수 개수
            //배열 index : 0부터 시작 ➡ n + 1
            for(int i = n + 1; i <= 2 * n; i++) {
                if(!prime[i]) {
                    count++;
                }
            }
            System.out.println(count);
        }	
    }
	
    //소수 찾기
    public static void get_prime() {
        //0, 1 : 소수 X ➡ true
        prime[0] = prime[1] = true;
		
        for(int i = 2; i <= Math.sqrt(prime.length); i++) {
            if(prime[i]) {
                continue;
            }
            for(int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
}

 

2. BufferedReader

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
    /*
    n > 123456 ➡ 2n : 최대 246912
    배열 index : 0부터 시작 ➡ 246912 + 1
    */
    public static boolean[] prime = new boolean[246913];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        get_prime(); //소수 찾기
		
        while(true) {
            int n = Integer.parseInt(br.readLine());
            if(n == 0) {
                break;
            }

            int count = 0;
            for(int i = n + 1; i <= 2 * n; i++) { //배열 index : 0부터 시작 ➡ n + 1
                if(!prime[i]) {
                    count++;
                }
            }
            System.out.println(count);
        }
    }
	
    //소수 찾기
    public static void get_prime() {
        //0, 1 : 소수 X ➡ true
        prime[0] = prime[1] = true;
		
        for(int i = 2; i <= Math.sqrt(prime.length); i++) {
            if(prime[i]) {
                continue;
            }
            for(int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
}

 

3. BufferedReader + StringBuilder - 출력 횟수 줄이기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
    /*
    n > 123456 ➡ 2n : 최대 246912
    배열 index : 0부터 시작 ➡ 246912 + 1
    */
    public static boolean[] prime = new boolean[246913];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        get_prime(); //소수 찾기
 
        while(true) {
            int n = Integer.parseInt(br.readLine());
            if(n == 0) {
                break;
            }
            
            int count = 0;
            for(int i = n + 1; i <= 2 * n; i++) { //배열 index : 0부터 시작 ➡ n + 1
                if(!prime[i]) {
                    count++;
                }
            }
            sb.append(count).append('\n');
        }
        System.out.print(sb);
    }
	
    //소수 찾기
    public static void get_prime() {
        //0, 1 : 소수 X ➡ true
        prime[0] = prime[1] = true;
		
        for(int i = 2; i <= Math.sqrt(prime.length); i++) {
            if(prime[i]) {
                continue;
            }
            for(int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
}

 

4. BufferedReader + StringBuilder + count_arr() - 출력 & 카운팅 횟수 줄이기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
    /*
    n > 123456 ➡ 2n : 최대 246912
    배열 index : 0부터 시작 ➡ 246912 + 1
    */
    public static boolean[] prime = new boolean[246913];
 
    //1 부터 누적 ➡ 각 index에 소수의 개수 담을 배열
    public static int[] count_arr = new int[246913];
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        get_prime(); //소수 찾기
        get_count(); //소수의 개수 담긴 배열
 
        while(true) {
            int n = Integer.parseInt(br.readLine());
            if(n == 0) {
                break;
            }
 
            //2n 까지의 소수의 개수 - n 까지의 소수의 개수
            sb.append(count_arr[2 * n] - count_arr[n]).append('\n');
        }
        System.out.print(sb);
    }
	
    //소수 찾기
    public static void get_prime() {
        //0, 1 : 소수 X ➡ true
        prime[0] = prime[1] = true;
		
        for(int i = 2; i <= Math.sqrt(prime.length); i++) {
            if(prime[i]) {
                continue;
            }
            for(int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
    
    //소수의 개수 담기
    public static void get_count() {
        int count = 0;
        for(int i = 2; i < prime.length; i++) { //2부터 시작
            if(!prime[i]) {
                count++;
            }
            count_arr[i] = count;	
        }
    }
}

---

성능

1. BufferedReader + StringBuilder + count_arr()
2. BufferedReader + StringBuilder
3. BufferedReader
4. Scanner

 

---

출처 : https://st-lab.tistory.com/85