소수 (Prime) 판별하기 - 제곱근 활용 소수란, 1과 자기 자신만을 약수로 가지는 수를 뜻한다. 예를 들어, 6은 1, 2, 3, 6을 약수로 가지기 때문에 소수가 아니지만,7은 1과 7(자기 자신) 을 약수로 가지기 때문에 소수이다. 주어진 수 n이 소수인지 아닌지는 어떻게 판별할 수 있을까?n을 2부터 (n-1)까지의 수로 나누어서, 나누어 떨어지는 수가 없으면 그 수는 소수일거다.하지만 n이 소수인 동시에 너무 큰 숫자라면, 하나하나 나누어 보기에는 매우 비효율적이다.그렇기 때문에, n의 제곱근을 이용하면 매우 효율적이게 값을 구할 수 있다. n의 제곱근 m을 구한다.n을 2부터 m까지 차례로 나누어 보았을 때, 나누어 떨어지는 수가 있다면 그 수는 소수가 아니다.반대로 m까지 나누어보았음에..