Jazz it Up!
시간 제한1초메모리 제한512 MB
3 이상 100000 이하의 제곱수 없는 정수 n이 주어질 때, 2 <= m < n이면서 m*n도 제곱수 없는 정수가 되는 m을 찾는다.
문제
친구 몇 명과 함께 여러분은 무조율 타악기와 첼로 밴드(Band of Atonal Percussionists and Cellists)를 결성했다. 몇 년째 함께 연주해 왔지만, 지금의 연주 수준에 만족하지 못한다. 흥미로운 새 스타일을 조사하던 중, 재즈 세계의 정교한 면모에 사로잡혔다.
물론 배운 것을 당장 모두 적용할 수는 없으니, 밴드가 연주하는 음악에 멋진 새 리듬 패턴을 즉흥적으로 넣는 것부터 시작하려 한다. 각 마디에 박자가 n개 있고, 각 박자를 m개의 음으로 나누어 연주한다. 따라서 마디마다 총 nm개의 음이 있다.
밴드의 모든 구성원은 재즈에 어울리지 않는 것은 용납하지 않는다는 것을 안다. 따라서 한 마디의 음 개수는 제곱수가 아니어야 한다. 즉, 한 마디의 음 개수를 k^2으로 나누는 k > 1인 수가 없어야 한다.
타악기 연주자는 이미 마디당 박자 수 n을 제안했다. 이제 남은 것은 제곱수가 끼어들 틈이 없는 박자당 음 개수를 찾는 것이다.
두 번째 예시에서 n = 30, m = 7이다. 2 ≤ m < n이고 m × n = 210은 k > 1인 어떤 k에 대해서도 k^2으로 나누어지지 않으므로 이 값이 성립한다.
입력
- 입력은 제곱수가 아닌 하나의 정수 3 ≤ n ≤ 105이다.
출력
- m × n이 여전히 제곱수가 아닌 정수 2 ≤ m < n을 출력한다.
가능한 답이 여러 개라면 아무거나 하나를 출력해도 된다.