[Baekjoon] 4948 베르트랑 공준
[Silver II] 베르트랑 공준 - 4948
성능 요약
메모리: 25728 KB, 시간: 208 ms
분류
수학(math), 정수론(number_theory), 소수 판정(primality_test), 에라토스테네스의 체(sieve)
문제 설명
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)
자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.
입력의 마지막에는 0이 주어진다.
출력
각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.
베르트랑 공준
베르트랑 공준(영어: Bertrand’s postulate), 베르트랑-체비쇼프 정리(영어: Bertrand-Chebyshev theorem), 혹은 베르트랑 가설은 정수론에서 소수들의 분포에 관한 정리다. 이에 따르면, 두 자연수 n과 2n 사이에 적어도 하나의 소수가 존재한다.
출처: 위키백과
알고리즘 과정
이 문제를 봤을 때 전에 풀었던 많은 소수 문제들과 비슷하게 에라토스테네스의 체를 이용해서 풀면 되겠다고 생각했다. 에라토스테네스 체가 뭔지 모르시거나 알고리즘을 보고 싶은 사람들은 블로그 전 글을 확인하거나 여기를 누르면 전 글로 이동한다.
결국에는 베르트랑 공준이라는 것은 n과 2n 사이에 하나의 소수는 있다는 것이다.
문제를 살펴보면 입력은 여러 개의 테스트 케이스로 이루어져 있고 종료하려면 0을 입력하라고 되어있다.
그래서 나는 이 문제를 While()문을 이용하기로 했다. While()문을 이용해서 무제한으로 입력을 받고 if()문을 이용하여 0을 입력하면 종료가 되게하면 이 문제는 해결된다.
간단하게 에라토스테네스 체가 뭔지 설명하자면 소수인 자신을 제외한 소수의 배수들을 차례대로 제거하여 소수만 남기는 알고리즘이라고 생각하면 된다.
일단 여기는 내가 푼 방식을 올리지만 풀고 나서 다른 풀이를 하신 분들을 살펴보니 훨씬 효율적으로 푸신 것 같다. 코드의 길이는 똑같겠지만 시간에 관하여는 제일 최악의 경우가 나이지 않을까 싶다…ㅠㅅ ㅠ
내가 푼 풀이는 그냥 에라토스테네스 체에 while()문으로 반복시킨 것에 지나지 않는데 사실상 이 문제는 N의 최대 범위가 지정되어 있고, 소수라는 것이 변하지 않는 것이니 그냥 prime() 배열에 한 번에 N의 최대치까지 true or false를 판단해놓고 while()문에서는 그저 입력과 소수가 몇개인지를 판단해주면 시간적인 측면에서 많이 줄어들 것 같기도하다.
코드
Leave a comment