51일차 (02-19-2021)

예정되어있던 시험이 9시에 시작되었다. 시험 내용을 대충 설명하자면 저번 유튜브API를 이용해 클라이언트를 구현하는 것과 거의 똑같았다. 다만, 서버를 직접 만들어 데이터를 응답해 주는것이 추가되었다. 테스트는 크게 두가지로 나누어지는데 클라이언트와 서버를 만드는 것이다. 구현하는 과정에서 뭔가 잘 안되는 부분이 많았는데 어찌저찌 하다보니 결국은 다 통과 하였다. 재밌게 하였던 것 같다. 더 자세한 내용은 아직 제출 기한이 끝나지 않았기 때문에 쓸 수가 없다.

그래서 오늘은 토이브라블럼의 문제를 풀다가 하나 알아낸 재밌는 수학적 공식을 기록해 보려고 한다.

에라토스테네스의 체

에라토스테네스의 체란 무작위의 숫자를 정해 그 숫자 까지에 있는 모든 소수를 구하는 방법이다. 비록 문과 출신이지만 고등학생 때 수학을 꽤나 좋아했었는데, 이건 처음 들어본다. (알고리즘을 풀다가보면 이러한 지식들이 상당히 중요하다고 느끼곤한다.) 방식에 대해서 설명하자면,

1. 2부터 소수를 구하고자하는 수 까지의 모든 수를 나열한다.
2. 2는 소수이므로 2를 제외한 모든 2의 배수를 지운다.
3. 남아 있는 수 중 3을 제외한 모든 3의 배수를 지운다.
4. 남아 있는 수 중 5를 제외한 모든 5의 배수를 지운다.
5. 남아 있는 수 중 7을 제외한 모든 7의 배수를 지운다.
6. 위 과정을 반복하면 소수를 구할 수 있다.

(참고: 위키백과-에라토스테네스의 체 -> 그림 설명이 아주 잘 나와있다.)

신기했다.

function solution(n) {
  const primes = new Array(n).fill(true); // 1
  primes[0] = false; // 2
  for(let i = 2; i ** 2 <= n; i += 1) { // 3
    if (primes[i - 1] === true) { // 4
      for (let j = i ** 2; j <= n; j += i) { // 5
        primes[j - 1] = false; // 6
      }
    }
  }
  return primes.filter(e => e).length; // 7
}

(참고: 프로그래머스-소수구하기)
위 코드는 검색하다 우연히 다른 분의 블로그에서 가져온 것이다. 일단 내가 짜기엔 너무나 힘든 알고리즘이라... 코드를 보고 분석을 해보았다.

1. 구하고자 하는 구간 n까지의 수를 모두 true로 표시.
2. primes[0] 즉, 1은 소수가 아니므로 false.
3. 2부터 n까지 검사를 하는데 조건이 i ** 2 즉, i의 제곱이 구하고자 하는 수의 범위를 넘어 가면 확인할 필요가 없으므로 연산은 상당히 줄어든다.
4. 숫자 i의 인덱스는 i - 1 이므로 만약 숫자 i가 true라면 for 반복문 실행
5. 초기값이 i ** 2 인 이유는 (2, 3, 5, 7) 은 자기 자신을 제외하기 때문.
6. 조건에 따라 j의 배수를 찾아서 false.
7. 배열의 true만 찾아서 길이를 계산하면 소수의 개수가 나온다.

정말 똑똑한 풀이법이다. 소수를 하나하나 찾는게 아니라 소수를 제외한 모두를 지워서 찾는 것.

만약 10까지의 소수를 구한다면,

1: [ false, true, true, true, true, true, true, true, true, true ]
2: [ false, true, true, false, true, false, true, false, true, false ]
3: [ false, true, true, false, true, false, true, false, false, false ]

가장 상위의 for문이 세번만 돌면 가능하다.