인프런 커뮤니티 질문&답변
작성한 질문수
10 : 33 쯤 질문 있습니다.
작성
·
191
2
안녕하세요 교수님. 강의를 듣던 중 궁금한 부분이 있어서 질문 드립니다.
10 : 33에서 div * div <= num으로 연산 횟수를 줄이셨는데
교수님 말 처럼 그냥 경험으로 쌓고 넘어가기엔 원리가 궁금해 도저히 머릿속에서 떠나질 않네요. 혹시 참고 할만한 자료나 설명이라도 있을까요? 조금 수학적인 내용이라 강의의 주제에서 벗어나긴 하지만 도움울 주실수 있으시다면 꼭 부탁드리고 싶습니다.
답변 2
10
교수님은 아니지만 답변 드려요..!😀
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 와도 같죠.
0