210617 TIL

오늘 한 것

소수 구하기 알고리즘에 대한 구체적인 이해하기

const 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;
};

소수를 구하는 것은 여러 알고리즘 문제를 푸는데 있어, 밑바탕이 되는 개념 인 것 같다.
이것을 활용한 수많은 문제가 있기 때문이다.

소수는 1과 본인만을 약수로 가지는 수이다.
따라서, 1을 초과한 그 어떤 수로도 나누었을 때 나머지가 생기면 안된다.

그래서 for 문을 1부터 자기 자신 수까지 돌리면 소수가 나온다.
다만, 이렇게 풀이했을 때 시간복잡도가 길어질 수 있어 여러가지 해법이 제시되었는데 아래와 같이 제시되었다.

1. loop를 자기 자신까지 돌리는 법 -> 가장 기초적인 방법
2. loop를 자기 자신의 /2 까지 돌리는 법 -> 조금 더 효율적인 방법
3. loop를 자기 자신의 제곱근까지 돌리는 법 -> 조금 더 더 효율적인 방법

그 이상 효율적인 '에라토스테네스의 체' 라는 개념으로 풀이 하기도 한다.

추가적으로 설명하자면, 예를 들어 16 의 소수 여부를 판단할 때
1~16까지 나누어 지는 수가 있는지 돌려봐도 되지만

나누는 수가 /2 넘어가면 약수의 위치만 바뀔 뿐 숫자는 같다

1 * 16
2 * 8
4 * 4
8 * 2
// 반복
16 *1

이러한 결과를 통해 /2 까지만 나누라는 것이 마치 공식처럼 통용되는 듯 하다. 제곱근도 마찬가지다.

1 * 16
2 * 8
4 * 4
// 반복
8 * 2
16 *1

1번 방법으로는 for문이 16번 실행되어야 하고,
2번 방법은 8번이 실행되어야 하고
3번 방법은 4번이 실행된다.

끝.