CS/Algorithm

제곱근이 무엇인가? 소수 판별에 사용하는 이유 알아보기

소수란 무엇인가?  소수는 수학의 기본적인 개념이면서도 흥미로운 특성을 가진 숫자입니다. 1과 자기 자신 외에는 어떤 자연수로도 나누어떨어지지 않는 수를 소수라고 하는데요. 예를 들어, 7은 소수이지만 8은 2, 4로 나누어떨어지므로 소수가 아닙니다. 소수는 어떻게 판별할까?  소수를 판별하는 가장 단순한 방법은 주어진 숫자를 2부터 시작해서 차례대로 나누어 보는 것입니다. 하지만 이 방법은 숫자가 커질수록 계산량이 기하급수적으로 늘어나 매우 비효율적입니다. 제곱근을 이용한 소수 판별  소수 판별에 제곱근을 사용하는 핵심적인 이유는 계산 효율성을 높이기 위해서입니다. 그 이유를 설명하기 위해서는 제곱근의 특징을 이해해야 하는데요, 그 이유는 다음과 같습니다. 약수의 대칭성: 어떤 수를 두 개의 수로 나눌..