Java) BOJ 4948. 베르트랑 공준
문제 링크
제한
- 시간 제한 : 1 초
- 메모리 제한 : 256 MB
문제
- 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
- 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
- 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)
- 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.
입력
- 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.
- 입력의 마지막에는 0이 주어진다. 1 ≤ n ≤ 123,456
출력
- 각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.
👀 풀이
- n초과 2n이하의 수들을 소수를 판별하는 연산을 해서 소수면 카운트해서 2n까지 판별이 끝나면 총 개수를 출력했다.
- 하지만 정직하게 2부터 i까지의 수의 나머지를 구하면서 소수를 판별하면 시간이 오래 걸리기 때문에 i의 제곱근 만큼만 반복하는 알고리즘을 썼다.
- i의 제곱근만큼만 반복해도 소수인지 판별이 되는 이유는 제곱근을 넘어가는 수 부터는 앞전에 구했던 곱해서 i가 되는 수들이 순서만 바뀌어서 똑같이 나오기 때문이다.
- 예를 들어 i=16라면
- 1*16
- 2*8
- 4*4
- 8*2
- 16*1
- 위와 같이 16의 제곱근인 4를 기점으로 앞전에 나왔던 수들이 순서만 바뀌어서 나온다.
-
그래서 제곱근을 초과하는 수에 대해 소수를 판별하는 연산을 하는 것은 생략해도 결과에 영향이 없다.
- 소수 구하기
- 예전에 참고했던 글인데 언어 상관없이 개념적으로 참고하기 좋은 글이다.
결과
- 시간 : 696 ms
- 메모리 : 14660 KB