소수를 구하는 방법(2) 제곱근의 이용

제곱근의 이용

n의 약수는 무조건 1 ~ √n의 범위에 존재한다.

 

✔️ 소수인지를 확인할 숫자 n의 제곱근  √n을 기준으로 약수끼리의 곱은 대칭으로 이루어진다

✔️ 그렇기 때문에  √n 이하의 작은 값까지만 검사를 하면 나머지는 검사를 할 필요가 없다

 

예를 들어 n = 18이라면, 18의 약수는 1, 2, 3, 6, 9, 18이다

이 때 n의 제곱근인 √18은 약 4.242이며, 이를 기준으로 약수의 순서를 보면 아래와 같다

 

(1 x 18)  (2 x 9)  (3 x 6)     √18 = 4.242    (6 x 3)  (9 x 2)  (18 x 1)

 

 

✔️ 제곱근을 기준으로 좌우의 연산이 대칭되는 형상을 가진다 (예) (3 x 6) √18 (6 x 3)

✔️ 그렇기 때문에 제곱근과 같거나 작은 숫자로 나누어지면, 그 이후는 대칭이므로 확인할 필요가 없다는 원리이다.

✔️ 즉, 제곱근 값 이하의 수만 확인하면 된다.

✔️ √18은 약 4.242 이므로, 4까지 확인했을 때 나누어  떨어지지 않으면 소수가 아니다