우편 묶음의 크기

문제

한 우체국에서 같은 배송 구역으로 보낼 안내 우편 N통을 준비했다. 직원은 우편을 여러 묶음으로 나눈 뒤 각 묶음에 끈을 하나씩 묶으려 한다. 모든 우편은 정확히 한 묶음에 들어가야 하며, 모든 묶음에 들어가는 우편의 수는 같아야 한다. 묶음을 만들고 남는 우편이 있어서는 안 된다. 묶음 하나에 넣는 우편의 수를 묶음 크기라고 한다. 우체국에서 사용하는 정리함에는 한 묶음에 최대 K통까지만 넣을 수 있다. 따라서 묶음 크기는 1 이상 K 이하인 정수여야 한다. 묶음 크기가 K보다 작아도 사용할 수 있지만, 크기가 K보다 큰 묶음은 사용할 수 없다. 묶음을 정확히 한 개만 만드는 것도 허용한다. 직원은 필요한 끈의 수를 줄이기 위해 사용할 수 있는 묶음 크기 중 가장 큰 값을 선택한다. 우편을 일부 빼거나 다른 우편을 추가할 수는 없으므로, 선택한 크기로 N통을 모두 나눌 수 있어야 한다. 크기를 선택한 뒤에는 모든 묶음이 같은 크기를 사용하므로 묶음을 만드는 순서나 개별 우편의 순서는 고려하지 않는다. 예를 들어 우편이 18통이고 정리함의 제한이 5통이면, 크기가 4인 묶음은 우편이 남으므로 사용할 수 없다. 크기가 3인 묶음은 우편이 남지 않으며 제한도 지킨다. 이 경우 사용할 수 있는 가장 큰 묶음 크기는 3이다. 우편 수 N과 정리함의 제한 K가 주어질 때, 직원이 선택할 묶음 크기를 구한다. 크기가 1인 묶음은 항상 만들 수 있으므로 답이 없는 경우는 없다. 출력할 값은 묶음의 개수가 아니라 묶음 하나에 넣는 우편의 수이다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000이다.

출력

조건을 만족하는 가장 큰 묶음 크기를 정수 하나로 출력한다.

18 5

3

17 10

1

12 20

12

출처: Devin.KR 자체 제작