백준 15965번 문제 링크
문제 이름 : K번째 소수
주 언어 : Python
태그 : 수학 / 정수론 / 소수 판정 / 에라토스테네스의 체
solved.ac 등급 : Silver II (2023/05/02 확인)
문제 보기
문제 :
(문제 일부 생략)
한결이를 도와 k번째 소수를 알려주자.
소수의 정의는 다음과 같다.
2 이상의 자연수 N이 1과 N을 제외하고 어떤 자연수로도 나누어 떨어지지 않을 때 소수라고 한다.
입력 :
자연수 K가 주어진다.(1 ≤ K ≤ 500,000)
출력 :
K번째 소수를 출력하자.
소수 에 대한 문제인데, 그 중에서도 $n$번째 소수 $p_{n}$에 대한 문제입니다.
갑자기 뜬금없는 결과지만, $n \geq 6$이면 $p_{n} < n \left( \ln n + \ln\ln n \right)$ 임이 알려져 있습니다. ($\ln n$은 자연로그함수 입니다.)
$n = 500000$이면, $\ln n + \ln\ln n = 15.6966812...$이므로, 50만번째 소수는 대략 7848340보다 작다는 것을 알 수 있습니다.
따라서, 에라토스테네스의 체 로 적당히 800만 정도까지의 소수 리스트를 받아서, 그 리스트의 n번째 원소를 얻어주면 되겠습니다.
인덱스 0에 2가 들어가기 때문에, N번째 소수는 인덱스 N - 1에 있습니다.
이 문제를 푸실 수 있다면, 백준 09842번 - Prime 도 쉽게 풀 수 있습니다. 1만번째까지의 소수를 구하면 되기 때문입니다.
여담으로, 실제 50만번째 소수는 7368787 입니다.
-번째 푼 문제 (2022/--/--)