스파르타 알고리즘 트랙 문제 1일차 - 2 #4948 베르트랑 공준

문제

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

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

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

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

 

해결 과정

2부터 그 숫자의 제곱근보다 작은 자연수까지 나누었을 때 나누어 떨어지는 자연수가 없다면 그 숫자는 소수임을 알 수 있다.

import java.util.Scanner; import static java.lang.Math.sqrt; public class Main {     public static void main(String[] args) {         while(true){             int ans = 0;             int check = 0;             Scanner a = new Scanner(System.in);             int n = a.nextInt();             if (n == 0)                 break;             int n2 = n*2;             for (int i = n+1;i<=n2;i++){                 for (int j = 2;j<=sqrt(i);j++){                     if(i < j)                         break;                     if (i%j==0){                         check = 1;                         break;}                 }                 if (check == 0){                     ans++;                     check = 0;                 }             }             System.out.println(ans);         }     } }

변수 i를 통해 n부터 2n 사이의 자연수를,  변수 j를 통해 2부터 i의 제곱근까지의 자연수를 대입해 나누어 떨어지는 j가 있을 경우는 무시, 그 외의 경우를 계산해 출력하도록 하였다. 또한 n의 값을 여러번 반복해서 입력할 수 있되 입력된 n이 0일 경우 프로그램을 종료하도록 하기 위해 while의 조건에는 true로 무한 반복을 구현하였고 while 내부에 입력값이 0인 경우 while문을 탈출하도록 코드를 작성하였다.

 

위의 코드를 제출했을 때 돌아온 답변은 "런타임 에러 (NoSuchElement)"이었다. 원인은 존재하지 않는 것을 가져오려고 할 때 발생하는데, 값을 불러올 때 입력된 데이터가 끝났음에도 EOF로 판단하지 않아 추가로 입력을 받으려고 시도했기에 발생한 에러였다. 따라서 입력이 종료되었기에 불러올 데이터가 없다는 것을 설정해 두는 것이 필요했다.

 

따라서 while문 내부에 추가 입력이 있을 경우 실행될 수 있도록 hasNextInt()를 조건에 추가해 입력이 없다면 불러오지 않도록 코드를 수정하였다.

import java.util.Scanner; import static java.lang.Math.sqrt; public class Main {     public static void main(String[] args) {         Scanner a = new Scanner(System.in);         while(a.hasNextInt()){             int ans = 0;             int check = 0;             int n = a.nextInt();             if (n == 0)                 break;             int n2 = n*2;             for (int i = n+1;i<=n2;i++){                 for (int j = 2;j<=sqrt(i);j++){                     if(i < j)                         break;                     if (i%j==0){                         check = 1;                         break;}                 }                 if (check == 0){                     ans++;                     check = 0;                 }             }             System.out.println(ans);         }     } }

위의 코드를 제출했을 때 런타임 에러는 수정되었지만, 틀렸다는 답변이 돌아왔다. 

코드를 다시 찬찬히 살펴본 결과, for문에서 값이 1로 변경된 변수 check를 다시 사용할 때 초기화하지 않아서 계속 1인 상태로 진행되는 것이 보였다.

 

import java.util.Scanner; import static java.lang.Math.sqrt; public class Main {     public static void main(String[] args) {         Scanner a = new Scanner(System.in);         while(a.hasNextInt()){             int ans = 0;             int check = 0;             int n = a.nextInt();             if (n == 0)                 break;             int n2 = n*2;             for (int i = n+1;i<=n2;i++){                 check = 0;                 for (int j = 2;j<=sqrt(i);j++){                     if (i%j==0){                         check = 1;                         break;}                 }                 if (check == 0){                     ans++;                 }             }             System.out.println(ans);         }     } }

for문 앞에 check 값을 0으로 초기화한 후에는 정답이라는 답변을 받을 수 있었다.