제곱근 소수 구하기
핵심 : 제곱근까지만 구하기
function isPrime(num) {
if (num === 1) return false;
for (let i = 2; i <= parseInt(Math.sqrt(num)); i++) {
if (num % i === 0) return false;
}
return true;
}
첫줄 if문 부터 설명을 하자면
if (num === 1) return false;
1은 소수가 아니라
약수가 없는 유일한 자연수이기 때문에
처음에 구분하는 로직을 작성해준다.
1이 들어오게 되면 1은 소수가 아니므로 false 리턴 / 바로 끝
이후 for문부터 예를 들어보자면 예를 들어보자면
for (let i = 2; i <= parseInt(Math.sqrt(25)); i++)
25의 제곱근은 5이기 때문에
for (let i = 2; i <= 5; i++)
이거랑 같이 표현할 수 있다.
혼동하면 안되는게 여기까진 소수인지 아닌지 판별도 안한거다.
그냥 제곱근으로 포문 줄이는걸 줄여준거다.
혹시 저게 왜 줄여준거냐 하시는 분들을 위해
: 처음 궁금했던건 n이 소수이냐? 인데
제곱근을 썼을 때 떡하니 떨어지는 순간 6부터의 포문은 돌 필요가 없기 때문이다.
놀랍게도 이건 모든 숫자에 먹힌다.
그 이유는
N의 약수는 무조건 sqrt(N)의 범위에 존재하기 때문이다.
다음 코드로 넘어가겠다.
if (num % i === 0) return false;
여기서 num에 나도 모르게 제곱근을 거치고 난 이후에 숫자를 집어넣었는데,
그게 아니라 원래 num 즉, 25를 넣어야한다.(나만 착각한걸수도 있음)
오히려 제곱근의 영향을 받는건 i이다. 그만큼 적게 도는거니까.
여튼 이 if문으로 소수를 판별하는 것이다.
제곱근까지 돌았을 때 나머지가 0인게 한번이라도 있다면
소수가 아니므로 false가 되는거고
제곱근까지 다 돌아도 나머지가 0 인게 없다면 true(소수)가 되는 것이다.
Num이 소수라면?
for (let i = 2; i <= parseInt(Math.sqrt(23)); i++)
난 엄청 헷갈렸기 때문에 자세하게 작성할 생각이다.
위의 예는 25라서 parseInt가 사용될 일이 없지만
23과 같은 소수라면?
대충 계산기를 뚜드려보니 4.7xxx이 나오고 그걸 parseInt 하니 4가 된다.
if (num % i === 0) return false;
이후 i는 2 , 3 , 4 가 차례대로 들어가고
23 % 2 , 3 , 4 를 순차적으로 했을 때 나누어떨어지는게 없다면
그 수는 소수가 되는 것이다.
