[JAVA 알고리즘]BAEKJOON 4948번 베르트랑 공준

베르트랑 공준

---

문제 설명

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

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

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

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

제한사항

• 1 ≤ n ≤ 123,456

입력

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

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

출력

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

입출력 예

answers	return
1 10 13 100 1000 10000 100000 0	1 4 3 21 135 1033 8392

---

나의 문제풀이

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int answer = 0;
		int cnt = 0;
		
		// n < i <= 2n 의 소수의 개수
		// 반복문을 이용해서 n에서 2n까지 반복하면서 소수를 구한다.
		while (true) {
			int n = sc.nextInt();
			if (n == 0) break;
			
			for (int i = n+1; i <= 2*n; i++) {
				cnt = 0;
				
				for (int j = 2; j*j <= i; j++) {
					if (i % j == 0) {
						cnt++;
						break;
					}
				}
				if (cnt == 0) answer++;
			}
			
			// 0일경우 출력이 되지않아야한다.
			if (answer > 0) { 
				System.out.println(answer);
				answer = 0;
			}
			
		}
		
	}

}

• 스캐너를 통해서 입력값을 받는다.
• 입력값 마지막 0이 나오기전까지 반복될 수 있도록 반복문을 만들어준다.
• 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 수 안에서 소수를 찾아 값을 출력한다.

---

느낀 점

프로그래머스에서 하는 코딩연습과는 다르게 백준은 입력값을 받는거 부터 코딩을 해야되기 때문에 주어지는 입력값에 따라 어떤 방식을 쓰는가에 따라 시간과 메모리가 많은 차이를 보일 수 가 있어 입출력에 관해서도 좀더 공부가 되고 찾아봐야겠다.

 

소수를 구할 당시 아리스토테네스의 체에 관한 정보를 알지 못해 그냥 for문은 돌려 시간초과가 발생했는데 아리스토테네스의 체를 보고 조건만 바꿔주니 일딴 통과하였다.

for (int i = n+1; i <= 2*n; i++) {
    //for (int j = 2; j <= i; j++) { // 생으로 계산 시 시간 초과
    // 특정 범위내의 모든 소수를 찾는 경우 에라토스테네스의 체 방식이 가장 빠르다.
    // 에라토스테네스의 체를 이용하여 임의의 자연수에 대해 소수들의 배수를 제외한다.
    // 몫과 나누는 수 둘 중 하나는 N 제곱근 이하이기 때문에 j를 제곱으로 범위를 지정해준다.
    // 그러면 i의 제곱근까지의 수 중에서 소수를 찾아 반복횟수가 줄어든다.
    for (int j = 2; j*j <= i; j++) { 
		if (i % j == 0) {
			cnt++;
			break;
		}
	}
	if (cnt == 0) answer++;
}

BufferedReader의 사용으로 스캐너보다 빠른 입력이 가능하다.

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

public class Main {
	public static void main(String[] args) throws IOException { // throws를 작성해주어야한다.
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 선언
		// 입력값이 무조건 String이기 때문에 다른 타입으로 입력 받기 위해 형변환을 한다.
		int n = Integer.parseInt(br.readLine()); 
	}        
}

메모리는 적게 나오는데 시간이 매우 길게 나온다...