소수 찾기

자바스크립트로 소수 찾기

알고리즘 공부를 하며 소수를 찾는 문제를 자주 접하다 보니 정리를 하게 되었다.

소수란?

• 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수

2, 3, 5, 7 ...

반복문을 이용해 소수를 찾는 방법

function isPrime(num) {
  if(num===1) return false; // 1은 항상 소수가 아님
  if(num === 2) return true; // 2는 항상 소수
  if(num % 2 === 0) return false; // 2의 배수는 항상 소수가 아님
  for(let i=3; i<=parseInt(Math.sqrt(num)); i+=2){ // 따라서 3부터 시작
      if(num%i===0) return false; 				   // 시간복잡도를 위해 제곱근, 홀수만 반복
  }
  return true; 
}