10 : 33 쯤 질문 있습니다.

교수님은 아니지만 답변 드려요..!😀

12의 약수는 1 2 3 4 6 12 이렇게 있습니다. 

1x12 = 12, 2x6 = 12, 3x4 = 12 이렇게 되기 때문에 1은 12와 짝지어지고 2는 6과, 3은 4와 짝지어질 수 있다는 것을 알 수 있습니다. 

그래서 사실상 12라는 숫자가 소수인지를 판단하려면 대충 1,2,3 까지만 나눠보면 되는거에요! 2로 나눠지면 2의 짝꿍인 6은 보나마나 12의 약수일테니까 당연히 6으로도 나눠지겠죠! 

마찬가지로 16 이 소수인지를 판단해보려면 16의 약수는 1,2,4,8,16 이렇겐데 4까지만 나눠봐도 16이 소수인지 아닌지 판단할 수 있겠죠?  2와 8끼리 짝꿍이니 16이 2로 나눠진다면 당연히 8로도 나눠질테니 굳이 8로 안나눠 봐도 괜찮겠지요.

대충 이렇게 약수들이 서로 데칼코마니처럼 짝꿍이 되는 그 기준점이 "제곱근"입니다. 제곱근은 짝꿍이 자기 자신이니까요. (위에서 16의 제곱근인 4를 중심으로 양옆 약수들이 짝꿍이 되었죠) 그렇기 때문에 해당 수가 소수인지를 판단하려면 2부터 그 수의 제곱근까지만 나눠보아도 판단할 수 있는겁니다. 하나라도 나뉘어 떨어지는게 있다면 소수가 아니겠죠.

16 같은 경우엔 4를 기준으로 양 옆 약수들이 서로 짝꿍이되고 12 같은 경우엔 대충 3 을 기준으로 양 옆 약수들이 서로 짝꿍이 되는 것을 확인할 수 있었죠.

그래서 num 을 2~num 까지의 수를 모두 나눠보려 할 때 굳이 전부 다 나눠볼 필요 없이 num 의 제곱근이 되는 수까지만 검사를 해봐도 num이 소수인지 아닌지를 판단할 수 있으므로 반복식이 div * div <= num;  이 되는 것입니다.

이 식은 div <= 루트(num)  와도 같으니까요!  div * div <= 16 은 곧 div <= 4 와도 같죠.

해결 되었습니다. 좋은 답변 감사드려요!