• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

다른 분들의 질문을 보면 Math.sqrt, num / 2 하는 것을 볼 수 있는데...

22.12.14 16:11 작성 조회수 192

0

저렇게 하시는 이유가 뭔지 궁금합니다 ㅠㅠ

구글링해보았을 때도 비슷한 케이스를 볼 수 있었는데 정확한 이유를 잘 모르겠습니다 ㅠㅠ

답변 1

답변을 작성해보세요.

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