백준 09842번 / 9842번 문제 링크
문제 이름 : Prime
주 언어 : Python
태그 : 수학 / 정수론 / 소수 판정 / 에라토스테네스의 체
solved.ac 등급 : Silver IV (2023/05/02 확인)
문제 보기
문제 :
A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. The first prime number is 2. Can you write a program that computes the n-th prime number, given a number n ≤ 10000?
(축약 & 번역) - 소수는 정확히 약수가 두 개 (1과 자기자신) 뿐인 수 입니다. 첫번째 소수는 2입니다. n (n ≤ 10000) 번째 소수를 구하실 수 있습니까?
입력 :
The input contains just one number which is the number n as described above. The maximum value of n is 10000.
(축약 & 번역) - 한 줄에 10000 이하의 양의 정수 n이 입력됩니다.
출력 :
The output consists of a single integer that is the n-th prime number.
(축약 & 번역) - n번째 소수를 출력하십시오.
소수 에 대한 문제인데, 그 중에서도 $n$번째 소수 $p_{n}$에 대한 문제입니다.
갑자기 뜬금없는 결과지만, $n \geq 6$이면 $p_{n} < n \left( \ln n + \ln\ln n \right)$ 임이 알려져 있습니다. ($\ln n$은 자연로그함수 입니다.)
$n = 10000$이면, $\ln n + \ln\ln n = 11.5129...$이므로, 1만번째 소수는 대략 115129보다 작다는 것을 알 수 있습니다.
따라서, 에라토스테네스의 체 로 적당히 12만 정도까지의 소수 리스트를 받아서, 그 리스트의 n번째 원소를 얻어주면 되겠습니다.
인덱스 0에 2가 들어가기 때문에, N번째 소수는 인덱스 N - 1에 있습니다.
사실 2부터 하나하나씩 소수 판별 해서 N번째로 소수로 판별된 수를 출력해줄 수도 있지만 오히려 더 오래걸리고 구현도 귀찮아지니 에라토스테네스의 체가 더 낫습니다.
여담으로, 실제 1만번째 소수는 104729 입니다.
-번째 푼 문제 (2022/--/--)