소수의 정의는 1보다 큰 자연수 중 1 과 그 수 자기 자신만을 약수로 갖는 자연수를 의미한다는 점은 누구나 알고 있을 것이다.
즉, 소수의 약수는 2개만을 갖고, 그 중 하나는 반드시 1 이며, 나머지는 자기 자신만을 약수로 갖기 때문에 만약 1 보다 크고 자기 자신의 수보다 작은 자연수를 약수로 갖게 된다면 이는 합성수라고 한다.
그리고 위의 개념을 확장해본다면 합성수는 3개 이상인 자연수의 곱으로 이루어져 있으며 소수로 이루어진 곱으로 표현할 수 있다.
그리고 이를 소인수분해라고 한다.
더욱 개념을 넓혀볼까.
소수는 1과 자기 자신만을 약수로 갖고, 합성수는 3개 이상인 자연수의 곱으로 이루어져 있으며 소수들로 이루어진 곱으로 표현할 수 있다고 했다.
1 보다 큰 자연수는 모두 소수 또는 합성수로 이루어져 있으니 1 보다 큰 모든 자연수는 소수들의 곱으로 표현할 수 있다.
이렇듯 소수는 수학적으로도 매우 중요한 개념이다.
그렇다면 왜 개발자 입장에서 또는 프로그래밍의 세계에서 소수가 중요한 이유는 무엇일까.
바로 "암호" 때문이다.
실제로 우리 일상생활에서도 많이 쓰이는 암호 또한 소수를 이용하고 있다.
대표적으로 **'RSA 암호화 방식'**이 있다.
**소수를 루트로 구하는 법!!!
" √N 이하의 자연수들로 모두 나눠본다. "
방법 1 의 방법에서 약간 업그레이드 된 알고리즘이다.
바로 N 을 √N 이하의 자연수들만 나누는 방법이다.
왜 √N 이하의 자연수들만 나누면 되는지는 생각보다 매우 쉽게 알 수 있다.