백준 4948번 문제풀이 - 베르트랑 공준

백준 4948번 문제

 

 

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

4948번: 베르트랑 공준

임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용이다.

이에 따라 n을 입력 받고 n보다 크고 2n보다 작거나 같은 소수의 개수를 출력하도록 한다.

 

 

 

 

 

코딩

1. 나의 풀이

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

public class Bertrand {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n;
        // 1 <= n <= 123,456 범위를 가지기 때문에 2배의 +1인 246913개의 배열 생성
        boolean[] prime = new boolean[246913];
        Arrays.fill(prime, true); // true가 소수가 되도록 초기값설정
        prime[0] = prime[1] = false; // 0, 1은 소수가 아님

        for (int i = 2; i <= Math.sqrt(prime.length); i++) {
            if (!prime[i]) { // false의 경우 스킵
                continue;
            }
            // 소수가 아닌 수를 찾아 false로 설정
            for (int j = i * i; j <= prime.length; j += i) {
                prime[j] = false;
            }
        }
        // 0이 입력되기 전까지 반복문 실행
        do {
            n = Integer.parseInt(br.readLine());
            int count = 0; // 소수카운트
            // n보다 크고 2n보다 작거나 같은 소수 갯수 찾기
            for (int i = n+1; i <= 2*n; i++) {
                if (prime[i]) {
                    count++;
                }
            }
            if (count != 0) {
                sb.append(count).append('\n');
            }
        } while (n != 0);
        System.out.println(sb);
    }
}

 

2. 소수의 개수가 몇 개인지 세는 배열 메소드를 만들어, 반복문마다 셀 필요 없이 배열에 저장된 수를 출력하게 함.

(블로그 참고)

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

public class Bertrand2 {

    public static boolean[] prime = new boolean[246913];

    public static int[] count_arr = new int[246913];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        get_prime(); // 소수를 얻는 메소드 실행
        get_count(); // 소수의 개수가 저장된 배열을 얻는 메소드 실행
        StringBuilder sb = new StringBuilder();

        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) break;  // n이 0일 경우 종료
            // 2n까지의 소수의 개수 - n까지의 소수의 개수
            sb.append(count_arr[2 * n] - count_arr[n]).append('\n');
        }
        System.out.println(sb);
    }
    // 소수를 얻는 메소드
    public static void get_prime() {
        // 0과 1은 소수가 아니므로 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++) {
            if (!prime[i]) count++; // 소수일 경우 count를 증가
            // 0 ~ i까지의 소수의 개수 = count를 count_arr에 저장
            count_arr[i] = count;
        }
    }
}

 

 

 

 

 

결과

1.

2.

 

int 배열을 만들어 바로 출력하게 했을 때 메모리 사용량은 약간 증가했지만 속도가 빨라진 것을 볼 수 있다.

 

 

 

 

 

느낀 점

문제를 잘 푼 것 같아도 더 좋은 아이디어가 있을 수 있다는 생각을 항상 해야겠다. 메소드를 만들어서 활용하는 것도 자주 연습해야겠다고 느꼈다.

 

 

 

 

 

 

참고 : https://st-lab.tistory.com/85

[백준] 4948번 : 베르트랑 공준 - JAVA [자바]