[javaScript] for문과 제곱근 사용해서 소수인지 알아내기

1.문제 발생

 

for문을 활용해서 인자로 들어온 수가 소수인지 알아내서 소수가 맞다면 true, 소수가 아니라면 false를 return하는 문제가 있었다.

애초에 소수가 무엇인지만 알면 풀 수는 있지만, 잘! 풀기 위해선 좀더 생각해볼 소수의 특징들이 있어서 그걸 정리해봐야겠다 싶었다.

---

2.필요 개념

 

소수란 1과 자기 자신만을 가지는 정수를 말한다

 

소수의 특징
-1은 소수가 아니다.
-2는 소수이다.
-2를 제외한 짝수는 모두 소수가 아니다.
-다시말해, 2를 제외한 모든 소수는 홀수이다.

---

3.문제 해결 

 

방법01.

 

function isPrime(num) { 
  if (num===1){ //거름망01: 1은 소수가 아니다
    return false
  }
  if(num===2){ //거름망02: 2은 유일한 짝수인 소수이다
    return true
  }
  if(num%2===0){ //거름망03: 짝수는 소수가 아니다
    return false
  }
  for(let i=3;i<num;i+=2){ 
  	//거름망01~03을 거친 3이상의 홀수를 약수가 있나 없나 for문 돌리기
    if(num%i===0){ //거름망04: 약수로 나누어지면 소수가 아니다
      return false
    }
  }
  return true 
}

다짜고짜 for문을 돌리지 않고 먼저 if문으로 소수의 특징을 걸러주고 마지막에 가장 노가다인 for문을 돌려주면 효율적으로 소수가 걸러진다.

 

 

 

방법02.

 

제곱근의 특징을 이용해 더 효율적으로 풀 수 있다.

 

Advanced 개념
 약수를 구하여 소수인지 알아볼 때, 소수인지 알아보려는 수의 제곱근 전까지만 나눠보면 더욱 빠르다

 

예를 들어 아래의 이미지를 참고하자.

 

 

function isPrime(num) { 
  if (num===1){ //거름망01: 1은 소수가 아니다
    return false
  }
  if(num===2){ //거름망02: 2은 유일한 짝수인 소수이다
    return true
  }
  if(num%2===0){ //거름망03: 짝수는 소수가 아니다
    return false
  }
  for(let j=3;j<=Math.floor(Math.sqrt(num));j+=2){ 
  	//거름망01~03을 거친 3이상의 홀수를 약수가 있나 없나 for문 돌리기
    //단 숫자의 제곱근까지만 약수를 체크한다. (제곱근의 소숫점은 떼버린다.)
    if(num%j===0){//거름망04: 약수로 나누어지면 소수가 아니다
      return false
    }
  }
  return true 
}

---

5. 결론

• 소수의 특징과 소수의 정의를 잘 알아둔다.
• 소수를 divider숫자를 활용해서 체크할때 제곱근 트릭을 활용한다.
• for문을 돌리기 전에  if로 체크해서 불필요한 조건들을 걸러주면 코딩 테스트에서 좋은 점수를 받기도 한다고 한다.