-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
다른 분들의 질문을 보면 Math.sqrt, num / 2 하는 것을 볼 수 있는데...
22.12.14 16:11 작성 조회수 153
0
저렇게 하시는 이유가 뭔지 궁금합니다 ㅠㅠ
구글링해보았을 때도 비슷한 케이스를 볼 수 있었는데 정확한 이유를 잘 모르겠습니다 ㅠㅠ
답변을 작성해보세요.
0
김태원
지식공유자22.12.18 05:02
안녕하세요^^
그냥 수학지식입니다.
어떤 숫자가 소수인지 확인해 보려면 2부터 그 숫자의 제곱근까지에서 약수가 없으면 소수입니다.
만약 36이 소수인지 알고싶으면 2부터 6까지에서 36의 약수가 존재하는지 확인하면 됩니다.
36의 약수들을 살펴보면 아래와 같습니다.
36 = 1 * 36
36 = 2 * 18
36 = 3 * 12
36 = 4 * 9
36 = 6 * 6
36의 약수들입니다. 2부터 6까지만 확인하면 그 짝궁들은 자연스럽게 존재유무가 확인되는 거죠.
num / 2를 하는 이유는 1와 자기자신을 빼면 2부터 자기자신의 절반까지에서 약수는 존재합니다.
위에 36같은 경우 1 36 을 빼면 약수는 2부터 18까지에서만 존재합니다. 36 = 2 * 18
답변 1