[Algorithm] JavaScript, Level1. 소수 찾기

---

 

#1. 소수 찾기

 

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

제한조건

• n은 2이상 1000000이하의 자연수입니다.

 

입출력 예

n	result
10	4
5	3

 

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

풀이

function solution(n) {
  // 소수값을 넣을 배열 선언
  let result = [];
  // 0과 1은 소수가 아니기 때문에 2부터 파라미터로 받은 값 n까지 배열에 대입한다
  for(let i = 2; i < n+1; i++) result[i] = i;
  
  // 2부터 n까지 반복문을 돌면서
  for(let i = 2; i < n+1; i++) {
    // 각 인덱스의 값이 0이 아니라면
    if(result[i] !== 0) {
      // 각 인덱스 값의 배수들에
      // (i값이 2라면 j값은 2*2, 즉 4가 되고, 한 바퀴를 돌면 j값에 2를 더해 6이 되고, 8이 되는 방식)
      for(let j = i*2; j < n+1; j+=i) {
        // 0을 대입한다
        result[j] = 0;
      }
    }
  }
  // 배열에서 0이 아닌 수를 추출하여 그 길이를 반환한다
  return result.filter(v => v !== 0).length;
}

// 호출
solution(10);
solution(5);

 

결과

 

소감

어떻게 접근해야할지 한참을 고민하다가 결국 구글링하여 풀이 방법을 찾아낸 문제였습니다.

이 문제는 에라토스테네스의 체 라는 수학적 지식이 있어야 풀 수 있는 문제로, 1레벨 문제임에도 불구하고 접근조차 하지 못해 문과의 한계점이 들어났습니다.

하지만 반대로 에라토스테네스의 체 라는 정수론에 대해 공부할 수 있는 좋은 문제였습니다.

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위 만큼 배열에 할당하고, 이후 하나씩 지워나가는 방법론입니다.

간단히 말해

1. 배열을 생성하여 값의 범위를 초기화한다.
2. 2부터 시작해 특정 수의 배수에 해당하는 수를 모두 지운다. (지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
3. 2부터 시작하여 남아있는 수를 모두 출력한다.

위 와 같이 해결하면 되는 방법입니다.