백준 13319번 문제 링크
문제 이름 : 가짜 소수
주 언어 : Python
추가 언어 : TEXT
태그 : 수학 / 정수론 / 구성적 / 소수 판정 / 런타임 전의 전처리 / 페르마의 소정리
solved.ac 등급 : Gold I (2023/02/11 확인)
문제 보기
문제 :
지구이는 우연히 오일러 프로젝트에서 100억 정도의 매우 큰 숫자가 소수인지 판별해야만 풀리는 문제를 보게 되었다. 지구이는 $2$부터 $\sqrt{N}$까지 모든 숫자로 나누는 방법으로 코딩했지만, 1시간이 지나도 결과가 나오지 않았다. 결국 구글신에게 물어본 결과 “페르마 소정리”를 찾을 수 있었다. 페르마 소정리는 다음과 같다.
“소수 $p$와 $\gcd(a, p) = 1$인 모든 자연수 $a$에 대하여, $a^{p - 1} \equiv 1 \pmod{p}$이다.”
지구이는 이것을 응용해서 $n$이 소수인지 확인하기 위해 $2^{n - 1} \equiv 1 \pmod{n}$이면 소수라고 판별하기로 했다. 하지만 지구이의 코드는 $561$을 소수로 분류했고, 결국 또 틀리고 말았다. 이대로 포기할 수 없었던 지구이는 이것을 응용해서 $2$부터 $500$까지의 모든 숫자 $a$에 대하여 $a^{p-1} \equiv 1 \pmod{p}$을 만족할 때만 소수로 판별하기로 했다. 백만까지 컴퓨터로 확인을 해본 지구이는 자신만만하게 답을 제출했지만, 빨간 X표시가 반겨줄 뿐이었다.
지구이에게 반례 데이터를 알려주자!
지구이의 소수판별 코드는 여기에 있다.
입력 :
입력은 없다.
출력 :
첫 번째 줄에 자연수 $n$ ($500 < n \leq 10^{15}$)과 $n$의 소인수 $m$ ($1 < m < n$)을 출력한다. (출력 예시는 답이 아님에 주의하라.)
문제에서 $2^{n - 1} \equiv 1 \pmod{n}$ 을 만족하는 가장 작은 합성수인 Poulet Number $341$대신 가장 작은 카마이클 수 $561$을 예시로 준 지점에서 힌트를 얻을 수 있습니다.
$\gcd(a, n) = 1$인 모든 $a$에 대하여 $a^{n - 1} \equiv 1 \pmod{n}$인 합성수 $n$이 카마이클 수 이므로, 문제에서 $2 \leq a \leq 500$인 모든 $a$에 대하여 $a^{n - 1} \equiv 1 \pmod{n}$이려면 카마이클 수 $n$의 가장 작은 소인수가 $500$보다 커야한다는 것을 알 수 있습니다.
카마이클 수인지를 판단하기 위해서 코셀트 판정법 을 응용하여 $6m + 1$, $12m + 1$, $18m + 1$이 모두 소수 라면 $(6m + 1) (12m + 1) (18m + 1)$ 은 카마이클 수라는 정리를 이용해줍니다.
이 때는 $6m + 1 > 500$이면 되므로, 편의상 $m = 100$인 경우인 $601$, $1201$, $1801$이 소수인지 WolframAlpha에 검색해봤는데 (검색창에 N is prime? 이라고 치면 N이 소수인지 아닌지 알려줍니다.)
601 is Prime? / 1201 is Prime? / 1801 is Prime?
한번에 그냥 모두 소수로 나와서 당황했습니다.
$6m + 1 > 500$일 때 $6m + 1$, $12m + 1$, $18m + 1$이 모두 소수인지 일일히 소수판별법으로 판단해야하나 싶었는데 다행히도 그럴 일이 없었고, 다음과 같은 코드로 13319번을 통과했습니다.
가장 짧은 정답은 "9자리수" "3자리수" 인 듯 한데, 한번 이 수를 찾아보시는 재미도 있을 듯 합니다.
N번째 푼 문제 (2022/XX/XX)