문제 번호 4948번 : 베르트랑 공준 - JAVA [자바]

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

4948번: 베르트랑 공준

문제 설명

 

여러 숫자를 입력받은 후에 그 수부터 2n까지의 소수의 개수를 구하는 문제입니다.

 

문제 풀이

알고리즘은 에라토스테네스의 체 알고리즘을 사용했습니다. 이 알고리즘의 자세한 설명은 다음 게시물에 있습니다.

https://kkungchan.tistory.com/266

8단계 문제 번호 1929번 : 소수 구하기 - JAVA [자바]

이 알고리즘을 사용하여 전체를 while문으로 감싼후에 개수만 세어 출력하는 방식으로 코드를 만들었습니다.

import java.util.Scanner;

public class Main {
    public static boolean[] primBool;//해당 index가 소수인지 합성수인지 판별하는 배열
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = 1;

        while(true) {
            int primeCount = 0;

            n = sc.nextInt();

            if(n == 0){
                break;
            }
			
            prime_check((2 * n));

            for (int i = (n + 1); i < primBool.length; i++) {
                if (primBool[i] == false) {
                    primeCount++;
                }
            }

            System.out.println(primeCount);
        }
    }

    //배열에 index가 소수이면 false 아니면 true를 부여
    public static void prime_check(int n){

        /*
        에라토스테네스의 체 알고리즘
        기본적으로 배열이 모두 처음에 false이기 때문에 모두 소수라는 가정한다.
        소수의 반대는 합성수이다. 이 알고리즘은 합성수를 모두 걸러내는 형식으로 소수를 판별하는 알고리즘이다.
        합성수는 소수로 이루어진 곱이다. 예를 들어 2*2=4, 3*2*2=12 등등 모두 소수의 곱으로 표현할 수 있다.
        합성수의 또 특징은 가장 작은 소수의 배로 표현할 수 있다는 것이다. 12는 2*2*3으로 표현할 수 있지만 2의 6배로 표현 할 수 있다.
        9는 3의 3배로 표현할 수 있다. 이처럼 소수의 배수를 n까지 모두 제외 시킨 후에 소수를 판별하는 것이 에라토스테네스의 체 알고리즘이다.
         */
        primBool = new boolean[n+1];//boolean 배열을 초기화 하지 않을 경우 모두 false

        //배열은 0부터 시작한다. 하지만 자연수는 1부터 시작함으로 0은 아에 제외시키고 1은 소수가 아님으로 true로 만든다.
        primBool[0] = primBool[1] = true; //1은 소수에서 제외

        for(int i=2; i<=Math.sqrt(n); i++) {
            //이미 true로 합성수로 판별이 되었다면 넘어간다.
            if (primBool[i] == true) {
                continue;
            }

            /*
            해당 소수의 배수를 모두 true로 변경합니다.
            첫 수를 i+i가 아닌 i*i로 하는 이유는 속도 때문인데
            3+3의 경우 3*2로 이미 true이고
            4+4,4+4+4의 경우 4*2,4*3으로 이미 true이고
            5+5,5+5+5,5+5+5+5의 경우 5*2,5*3,5*4로 이미 true입니다.
            합성수의 제곱보다 작은 배우의 경우 이미 그 전에 합성수로 판별된 특징이 있습니다.
             */
            for (int j = i * i; j < primBool.length; j += i) {
                primBool[j] = true;
            }
        }
    }

}

 

감사합니다.