백준 4948 베르트랑 공준 [JAVA]

Ga0·2023년 5월 26일

baekjoon

목록 보기

57/123

문제 해석

0을 입력받을 때까지 임의의 자연수 N을 입력받아 N에 대하여 N보단 크고 2N보더 작거나 같은 소수의 개수를 구하면 되는 문제이다.
단, N은 1보다 같거나 크고 123,456보다 같거나 작다.

틀린 코드

import java.io.*;
import java.math.BigInteger;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    //입력&출력 부분
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        
        while(N != 0){
            countPrime(N); //소수 개수 버퍼에 저장하는 함수 호출
            N = Integer.parseInt(br.readLine());
        }

        br.close();

        bw.flush();
        bw.close();

    }

    //소수 개수 세기
    static void countPrime(int N) throws IOException {

        int count = 0; //소수의 개수를 세는 변수

        for(int i = N; i <= 2*N; i++){
            BigInteger bigNumber = new BigInteger(String.valueOf(i));

            if(bigNumber.isProbablePrime(10)){ //소수이면
               count++; //카운트 증가
            }

        }
        bw.write(count +"\n");
    }
}

틀린 결과

역시나... 시간 초과😞 (실버2인데 너무 쉽게 풀릴리가 없다.)
while문 안에 for문(countPrime 함수 안에 있는)이 있는 거나 다름이 없어서 중첩 반복문이 되었다. => 즉, 대략 시간 복잡도는 O(N²), 제한 시간이 1초인데 입력 값은 각각 1 ~ 123,456이니 O(N²) 일때는 제한시간에 1초를 맞추려면 입력 값을 최대 1만까지만 받을 수 있다.
그니까 문제가 된다... 입력 값이 1 ~ 123,456 이니 1만을 족히 넘을 수 있기 때문에!!!!

참고한 사이트

소수 구하는 알고리즘 이 사이트에 설명이 되어있는데, 간단히 요약하면 아래와 같다.

소수를 판별한다는 것은 결국 1과 자기 자신을 제외한 다른 자연수를 약수로 갖고 있으면 안된다는 의미
임의의 자연수 N (N > 0) 이 있다고 가정하자.
p × q = N 을 만족할 때 우리는 아래와 같은 부등식을 완성할 수 있는데( 1 ≤ 𝑝 , 𝑞 ≤ N )
p 와 q 중 하나는 √N 보다 작거나 같다.

예를 들어 N = 32 라고 하면 아래와 같이 표현할 수 있다.

		p x q
		1 x 32
		2 x 16
		4 x 8
		8 x 4
		16 x 2
		32 x 1
        
p가 증가한다면 q가 감소하고, 반대로 p가 감소한다면 q가 증가하는 것을 볼 수 있다.

p 와 q 는 N의 약수이기 때문에 결국 N 을 임의의 수로 나누게 되면 임의의 수가 √N 보다 작다면 결국 나머지는 √N 보다 클 수 밖에 없다는 것을 확인 할 수가 있다.
다시 말해 p 와 q 중 하나는 반드시 √N 보다 작거나 같다.
즉, √N 이하의 자연수 중에 나누어 떨어지는 수가 있다면 이는 1 과 N 을 제외한 다른 자연수가 N 의 약수라는 의미이므로 소수가 아니게 되는 것이다.

코드

import java.io.*;

public class Main {

    // N은 1보다 같거나 크고 123,456보다 같거나 작으니까
    // 또 N ~ 2N까지니까 최대 배열의 길이는 123,456 x 2 = 246912인데 1부터 시작하므로 246912 + 1 = 246913이다.
    static boolean[] primeNumber = new boolean[246913]; //소수 판별 배열

    //입력&출력 부분
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        countPrime(); //소수 판별 배열 만들기

        while(true){

            int N = Integer.parseInt(br.readLine());
            if(N == 0){
                break;
            }

            int count = 0; //소수 몇개인지 저장하는 변수

            for(int i = N+1; i <= 2*N; i++){ //N보단 커야하므로 +1
                //소수이면 배열에서 false인데 그거에 Not연산이니까 소수이면 카운트한다는 뜻
                if(!primeNumber[i])  count++;
            }

            bw.write(count + "\n");
        }

        br.close();

        bw.flush();
        bw.close();

    }
    //소수인지 판별하는 배열 만들기
    static void countPrime(){

        primeNumber[0] = primeNumber[1] = true; //0과 1은 소수가 아니므로 true

        for(int i = 2; i <= Math.sqrt(primeNumber.length); i++){

            if(primeNumber[i]) continue; //그냥 i 값 변경하지 않음

            for(int j = i * i; j < primeNumber.length; j += i) { //제곱이 걸릴 경우 true로 변경
                primeNumber[j] = true; //제곱근 x 제곱근 한 것은 제곱근으로 나눌 수 있으므로 true
            }
        }
    }
}