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

백준 4948번 문제 설명

문제 설명은 베르트랑 공준에 대해서 설명하고 있지만, 실제로는 중요한 부분이 아니고  자연수 n이 주어졌을 때, n보다 크고 2n보다 작거나 같은 수들 중 소수들의 개수를 구하는 코드를 짜는 것이 목표.

소수를 구하는 데 효율적인 방법은 해당 숫자를 나눌 수 있는 숫자가 있는 지 모든 숫자에 대해서 확인하는 것이 아니라, 소수에 대해서만 적용하면 되지만 코드가 복잡해지므로, 단순히 isPrime() 함수는 num이 주어졌을 때 num의 제곱근보다 작거나 같은 수 사이에서 나눠지는 지 확인.

 

 

 

for (int i = init; i <= 2 * n; i+=2) {
	if (isPrime(i)) {
		count++;
	}
}

이때 i모든 짝수는 2로 나뉘기 때문에 소수가 아니기에 +=2를 사용하였다. 같은 이유로 아래 코드와 같이 n이 홀수인 경우에는 n+1 값부터 소수인지 판별해도되지만 n+1는 무조건 짝수이기 때문에 초기화 값을 홀수로 지정해주었다.

if (n % 2 == 0) {
	init = n + 1;
} else {
	init = n + 2;
}

 

 

 

전체코드

import java.util.Scanner;
import java.lang.Math; 

public class Main
{
    public static boolean isPrime(int num) {
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int n;
	    int count;
	    while(true) {
	        count = 0;
	        n = sc.nextInt();
	        if (n == 0) {
	            break;
	        }
	        if (n == 1) {
	            System.out.println(1);
	            continue;
	        }
	        
	        int init;
	        if (n % 2 == 0) {
	            init = n + 1;
	        } else {
	            init = n + 2;
	        }
	        for (int i = init; i <= 2 * n; i+=2) {
	            if (isPrime(i)) {
	                count++;
	            }
	        }
	        System.out.println(count);
	    }
	}
}