[level 1] 소수 찾기

문제

 

풀이 코드

function solution(n) {
  let numArr = new Array(n).fill(1);
  for (let i = 2; i * i <= n; i++)
    for (let j = i * i; j <= n; j += i) numArr[j - 1] = 0;
  return numArr.reduce((sum, item) => sum + item, 0) - 1;
}

 

풀이 과정

어려운 문제였다 혼자 해결을 못하고 구글링을 통해 개념을 숙지했다

역시 나는 한참 부족하다

 

일단 소수찾는 알고리즘으로 에라토스테네스의 체 라는 개념을 알고 있어야 한다.

https://ko.wikipedia.org/wiki/에라토스테네스의_체

 

정말 간단히 설명하면 다음과 같다.

 

1. 소수가 아닌 수는 배수로 이루어진다.

2. 배수를 제거하면 남는 수들이 결국 소수가 된다.

 

이 개념을 바탕으로, 코드를 참고하여 작성하였다.

 

코드의 순서는 다음과 같다.

1. 우선, n 크기의 배열을 생성하고, 해당 배열에 fill 함수를 통하여 모든 요소를 1로 세팅한다.
2. 이전에 약수를 구하는 알고리즘과 마찬가지의 이유로, 모든 수를 비교 하는것은 시간적으로 너무 많이 낭비된다, 이를 해결하기 위해 제곱근으로 비교하며 for 루프를 돈다.
3. 순회 할때마다, 해당수의 배수에 해당하는 요소들의 인덱스를 0으로 설정한다. ( j - 1 )을 하는 이유는 인덱스는 0부터 시작하기 때문.
4. 그렇게 모든 수 까지 순회하고 나면, 소수가 위치한 인덱스만 1이된다.
5. reduce 함수를 이용해 모든 요소를 더해주면 소수의 갯수가 될것이다.
6. 단, 여기에는 1 도 포함되지만, 1은 소수가 아니므로 1을 빼준다.