시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 1105 | 277 | 242 | 29.476% |
지구이는 우연히 오일러 프로젝트에서 100억 정도의 매우 큰 숫자가 소수인지 판별해야만 풀리는 문제를 보게 되었다. 지구이는 2부터 sqrt(N) 까지 모든 숫자로 나누는 방법으로 코딩했지만, 1시간이 지나도 결과가 나오지 않았다. 결국 구글신에게 물어본 결과 “페르마 소정리”를 찾을 수 있었다. 페르마 소정리는 다음과 같다.
“소수 p와 (a, p) = 1인 모든 자연수 a에 대하여, a(p-1) ≡ 1 (mod p)이다.”
지구이는 이것을 응용해서 n이 소수인지 확인하기 위해 2(n-1) ≡ 1 (mod n)이면 소수라고 판별하기로 했다. 하지만 지구이의 코드는 561을 소수로 분류했고, 결국 또 틀리고 말았다. 이대로 포기할 수 없었던 지구이는 이것을 응용해서 2부터 500까지의 모든 숫자 a에 대하여 a(n-1) ≡ 1 (mod n)을 만족할 때만 소수로 판별하기로 했다. 백만까지 컴퓨터로 확인을 해본 지구이는 자신만만하게 답을 제출했지만, 빨간 X표시가 반겨줄 뿐이었다.
지구이에게 반례 데이터를 알려주자!
지구이의 소수판별 코드는 여기에 있다.
입력은 없다.
첫 번째 줄에 자연수 n(500 < n ≤ 1015)과 n의 소인수 m (1 < m < n)을 출력한다.
출력 예시는 답이 아님에 주의하라.
561 11