시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 52 29 27 64.286%

문제

지구이는 우연히 오일러 프로젝트에서 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

힌트

출처

Contest > 꼬마컵 > 꼬마컵 2016 I번