1. 풀이

숫자 n이 ab의 곱으로 표현할 수 있을때, a <= b라면 a는 n제곱근의 이하라는 간단한 규칙을 나타낸다.

2. 응용

2.1. 모든 약수 구하기

숫자 n의 모든 약수를 구할때, n의 제곱근 이하의 약수만을 구한 후 구한 약수값을 바탕으로 나머지 약수들을 구하면 빠르게 구할 수 있다.

• 48의 모든 약수구하기 : sqrt(48) = 6.928 -> 1, 2, 3, 4, 6 -> 48, 24, 16, 12, 8 -> 1, 2, 3, 4, 6, 8, 12, 16, 24, 48

2.2 에라토스테네스의 체

에라토스테네스의 체는 2, 3, 5… 순으로 소수의 배수를 지우면서 모든 소수를 구하는 방법이다. 문제는 어느 소수의 배수까지 검사해야 하는지 알아야 한다는 점이다. 위의 수식을 이용하면, N까지의 소수를 구할 경우 sqrt(N)이하의 소수의 배수까지만 구하면 된다는걸 쉽게 알 수 있다.

• 50까지의 모든 소수 구하기 : sqrt(50) = 7.071 -> 50 이하의 숫자 중에서 2, 3, 5, 7 소수의 배수를 지운다.

3. 참조

• 모든 약수 구하기 : http://egloos.zum.com/irakla/v/6291315