에라토스테네스의체

package quiz; import java.io.BufferedReader; import java.io.InputStreamReader; /** * 4948번 풀이 - 베르트랑 공준 * 베르트랑 공준은 임의의 자연수 n에 대하여, * n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. * 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. * 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) * * 자연수 n이 주어졌을 때, n보다 크고 2n보다 작거나 같은 소수의 개수를 구하여라. * **/ public class _4948 { public static void main(..

💡 👍🏻 [에라토스테네스의 체] 는 고대 그리스 수학자인 에라토스테네스가 만들어낸 소수를 판별하는 알고리즘이다. 마치 체를 가지고 수를 걸러내는 것 같아, '에라토스테네스의 채' 라고 부른다. 소수란 약수가 오로지 1인 수이다. 즉, 1을 제외한 수의 배수가 되는 수는 소수가 아니다. 소수를 대량으로 빠르고 정확하게 구할 때 이용한다. 지워지지 않은 수들이 소수이다. 에라토스테네스의 원리 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고 이후 하나 씩 지워가는 방법을 이용한다. 2부터 시작해서 특정 수의 배수에 해당되는 수를 모두 지운다. 2부터 시작해서 남은 수를 모두 출력한다. 🛠 예를 들어, 2부터 n까지의 수 중에서 소수를 구한다고 했을 때, 2는 소수니까 그대로 두고, n까지 순차..