소수(Prime Number) 구하기

알고리즘 문제에서 종종 등장하는 소수 구하는 로직은 국룰처럼 알고 있으면 좋다.
소수란 약수가 1과 자기자신뿐인 자연수를 뜻한다. (자연수란 1이상의 양의 정수)
즉, 변수가 소수인지 판별하려면 2부터 시작해서 변수-1까지 나누어 떨어지는 지 확인하면 된다.
나누어 떨어지면 나눈 수 역시 약수가 되므로 1과 자기자신 외에 또하나의 약수가 있으므로 소수가 아니게 된다.
나누어 떨어진다는 것을 코드로 표현하면 "변수 % i === 0"으로 나눈 나머지가 0이면 그 의미가 같다.

그런데 2부터 변수-1까지가 아니라의 변수/2 까지만 나눠봐도 된다.
예를 들어, 13이 소수인지 판별하려고 할 때, 13/2,13/3,13/4,13/5,13/6 에서 나누어 떨어지는 게 없으면 굳이 13/7인지를 확인할 필요가 없다. 소수가 아닌 12를 예를 들면 12/7~12/11은 결코 나누어 떨어질 수 없다.
이 논리를 코드로 표현해보면 아래와 같다.

const isPrime = function(number) {
  if(number <= 5) {
    if(number === 2 || number === 3 || number === 5) return true;
    else return false;
  } 
  for(let i = 2; i < number / 2; i++) {
    if(number % i === 0) return false; // 나누어 떨어지면 소수가 아니다.
  }
  return true; // 2부터 변수의 절반까지 모두 나눠봤을 때
}

아주 기초적인 알고리즘이니 숙지해두자.