250120 TIL - 소수 관련 알고리즘 팁

알고리즘 회고 - 소수 관련 팁

01) 개요

최근 알고리즘 문제에 소수와 관련된 이슈들이 많아서, 한 번 정리해보기로 결심했다!!

02) 소수 초급 판별법

소수는 1과 자기 자신만을 약수로 갖는 자연수지요? 그렇기 때문에 그 수가 소수인지 알아보는 가장 직접적인 방법은 1부터 그 숫자까지 1씩 더한 수들을 전부 나누기 해보고, 나머지가 0이 나오는 경우가 1과 본인인지 보는 방법이다!!

예시 코드

const isPrime = (num) => {
  let isPrime = true;
  // 1이랑 본인은 빼고 확인
  // 하나라도 자기 약수면 즉시 중단하고 false 반환
  for (let i = 2; i < num; i++) {
    if (num % i !== 0) {
      isPrime = false;
      break;
    }
  }
  return isPrime;
}

이리 하면 거의 num만큼의 수를 다 확인해야 할 수도 있어서 썩 좋지 않음!!!

03) 소수 중급 판별법

사실 약수들은 짝꿍이 있다!! 예를 들어 8이란 수의 약수는 1, 2, 4, 8인디, (1,8)과 (2,4)로 쌍을 이루지요?? 즉 어느 한 쪽의 약수를 알게 되면 이미 다른 쪽을 볼 필요도 없이 소수가 아닌 거니까? num의 절반만 확인해도 된다는 겨!! 만약 홀수여도 똑같음!!

예시 코드

const isPrime = (num) => {
  let isPrime = true;
  // num의 절반까지만 체크하기!!
  const half = num / 2;
  for (let i = 2; i < half; i++) {
    if (num % i !== 0) {
      isPrime = false;
      break;
    }
  }
  return isPrime;
}

이러면 하수의 방법보다 딱 봐도 절반만큼 복잡도가 줄어들지요? 아주 굿이에요 하지만 더 줄일 수 있다는 거?

04) 소수 고급 판별법

약수들은 서로 쌍을 이룬다는 것의 연장 선으로, 사실 num의 제곱근까지만 봐도 된다는 거? 다시 8의 경우를 보자!! 중수으 ㅣ방법을 쓰면 절반이 4니까 2, 3으로 두 개를 체크하게 될 텐데? 제곱근은 2 * √2로 약 2.8이니 2 하나만 체크해도 판별이 끝날 것임!! 더 줄었죠?

예시 코드

const isPrime = (num) => {
  let isPrime = true;
  // num의 제곱근까지만 체크하기!!
  const squareRoot = Math.sqrt(num);
  for (let i = 2; i < squareRoot; i++) {
    if (num % i !== 0) {
      isPrime = false;
      break;
    }
  }
  return isPrime;
}

사실 이러면 자연수와 실수의 비교라서 문제가 생길 수 있지만 일단 예시니까!! 무튼 소수 판별이 더 빨라졌다!!

초고수의 소수 판별법
통칭 "체"라고 해서, 자연수에서 소수일 수가 없는 넘들을 쳐내고 쳐내어 만든 소수 모음을 만들고, num이 해당 모음에 포함되는 지 확인한다거나 하는 등에 고오수 방법이 있는디, 있다는 것만 기억하고 혹시 필요해지면 찾아보자....!!!! 체가 여러 개여 또 흑흑