백준 4948 베르트랑 공준 (JAVA)

문제

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

제한

• 1 ≤ n ≤ 123,456

소수 응용 문제이다.

앞서 풀었던 방법처럼 제곱근을 활용하여 풀어보았다.

(앞서 풀었던 방법은 아래 링크 참조)

https://leopardcatstudio.tistory.com/100

백준 1929 소수 구하기 (JAVA)

 

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

/*
1. while(true) 0나올때까지 반복
2. N 입력
3. int DoubleN에 N*2 저장
4. 2중 for문으로 소수 검사
    -루트씨운 결과값으로 검사
    -2부터 검사
5. 출력
*/

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));

        while (true) {
            int N = Integer.parseInt(br.readLine());
            int DoubleN = N*2;
            int count = 0;
            int composite = 0;

            if(N == 2 || N == 1){
                //소수는 3 한개
                bw.write("1\n");
            }
            else if(N == 0){
                break;
            }
            else{
                
                for(int i=N+1;i<=DoubleN;i++){
                    for(int j=2;j<=Math.sqrt(i);j++){
                        if(i%j == 0){
                            composite++;
                        }
                    }
                    if(composite == 0){
                        count++;
                    }
                    composite = 0;
                }
                bw.write(Integer.toString(count)+"\n");
            }
            composite = 0;
            count = 0;
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

N을 입력받아 N+1 부터 N*2까지 소수인지 검사하는 코드를 작성했지만,

시간초과가 떠 버렸다...

이번에도 다른 블로그의 도움을 받아 작성해보았다.

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

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

흐름을 설명하자면,

 

문제에서 주어진 범위 1<= n <= 123456를 활용하여

1. 배열을 만들고

2. for문을 통해 배열의 합성수에 true 값을 넣는다

3. while문을 통해 배열이 false인 경우를 더한다

4. 더한값을 출력한다.

 

아래 작성한 주석을 보면 더 자세하게 설명해 놓았다! 참고하시길!ㅎㅎ

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

public class Main{
    
    //문제의 제한조건인 1 ≤ n ≤ 123,456
    //n의 최댓값인 123456*2+1한 값을 boolean배열의 범위로 설정합니다. 
    public static boolean[] prime = new boolean[246913];
    
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        get_prime();

        while(true){
            int n = Integer.parseInt(br.readLine());
            if(n==0) break;

            int count = 0;

            //n+1 ~ 2*n까지 prime배열이 거짓이면 count를 해줍니다.
            //count값이 소수의 값이기 때문에 출력해줍니다.
            for(int i=n+1;i<=2*n;i++){
                if(!prime[i]){count++;}
            }
            bw.write(Integer.toString(count)+"\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }

    //prime boolean 배열에 소수가 아닌 부분을 다 true로 채워줄 것입니다.
    public static void get_prime() {
        //0과 1은 소수가 아니므로 true
        prime[0] = prime[1] = true;

        //2부터 prime.length의 제곱근
        for(int i = 2; i<=Math.sqrt(prime.length);i++){
            //이미 true가 채워져있으면 pass
            if(prime[i]){continue;}
            //j에 i의 배수를 입력해가며, 해당하는 배열에 true값을 넣어줍니다.
            for(int j=i*i;j<prime.length;j+=i){
                prime[j] = true;
            }
        }

    }
}

세상은 넓고 고수는 많다!

문제를 풀면서 백준의 장점은 많은 선배들이 있다는 것이라는 생각이 들었다.

나보다 먼저 문제를 풀고 해설을 작성해주신 많은 선배님들 덕분에 짧은 시간안에 많은 것을 배울 수 있다.

감사합니다~!!