소수 p의 제곱근(\sqrt p)은 무리수라고 알려져 있다.

무리수는 유리수의 표현 방법 중의 하나인 분수 꼴로 나타내지지 않는 수이다.

하지만 그 수에 어느 정도 가까운 분수 꼴을 찾을 수 있을 것이다.

"가까운 분수"라는 말이 애매하기 때문에 분수 꼴을 나타낼 때 "분수의 분자와 분모에 쓰이는 숫자의 최대값을 자연수 n"으로 제한하기로 한다.

예를 들어 n이 4일 경우에는 1\over1, 1\over2, 1\over3, 1\over4 , 2\over1, 2\over3, 3\over1, 3\over2, 3\over4, 4\over1, 4\over3 의 11가지의 분수들 중에서 찾으면 된다.

2\over2, 2\over4, 3\over3, 4\over2, 4\over4 의 5가지 분수는 각각 1\over1, 1\over2, 1\over1, 2\over1, 1\over1 와 같이 약분되기 때문에 고려하지 않는다.

이런 조건을 만족하면서 \sqrt p 보다 큰 분수들 중에서 \sqrt p 에 가장 가까운 분수와 \sqrt p 보다 작은 분수들 중에서 \sqrt p 에 가장 가까운 분수를 찾으려고 한다.

예를 들어서 소수 p의 값으로 7이 주어지고 n이 20 이 주어지면 \sqrt 7 보다 큰 분수 중 가장 \sqrt 7 에 가까운 수는 8 \over 3 이고 \sqrt 7 보다 작은 분수중에서 가장 가까운 수는 13 \over 5 이 된다.

제곱근 timer 1s memory 64MB

제곱근 1s 64MB