에라토스테네스의 체 라는 개념을 읽어보면 n이 소수인지 아닌지 판별하기 위해서는 sqrt(n) 이하의 수만 나눠보면 된다고 한다. (sqrt는 루트를 의미함) 근데 왜 sqrt(n) 이하의 수를 나눠보면 알 수 있는 것인가? 감으로는 알 것 같으면서도 손으로 증명해 보려고 하니 잘 이해가 가지 않았고, 명쾌하게 해답을 주는 정보를 찾지 못해서 직접 생각해 보다 답이 나와 포스팅을 한다. 어떤 수 X가 합성수라고 하자. 그럼 X는 M x N의 형태로 나타날 수 있다. 그럼 여기서 M >= N 이라고 하자. 그럼 아래와 같은 식이 성립한다. -> X = M x N -> M x M >= M x N .... (N M^2 >= X (M x N = X) -> M >= sqrt(X) 즉 어떤 수 M의 최소값은 sqr..