[프로그래머스] 소수찾기** (에라토스테네스의 체 소수)

문제설명

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

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

• i! ≤ n

제한사항

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

입출력 예

n	result
10	4
5	3

2

입출력 예 설명

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

 

정답

function solution(num) {

// 숫자 0부터 확인하므로 num에 +1을 꼭해준다.
  let array = Array(num + 1).fill(true);
  
  // 0과 1은 소수가 아니니까 false 처리
  array[0] = false;
  array[1] = false;

// 2부터 num까지 숫자를 1씩 더하면서 확인한다.
  for (let i = 2; i * i <= num; i++) {
  
  // num의 i번째 배열이 true이면, (2,3,4,5..쭉 가므로..)
    if (array[i]) {
    
    // 그 배열의 제곱, 4, 9, 16, 25 .. 쭉쭊쭉 가서 false 처리 해준다.
      for (let j = i * i; j <= num; j += i) {
        array[j] = false;
      }
    }
  }
  
  // 모두 false처리를 마치고, array에 담긴 true값을 반환해 그 개수를 확인한다.
  return array.filter((a) => a).length;
}

console.log(solution(10));

---

1) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.

2) 2는 소수이므로 오른쪽에 2를 쓴다.

3) 자기 자신을 제외한 2의 배수를 모두 지운다.

4) 남아있는 수 가운데 3은 소수이므로 오른쪽에 쓴다.

5) 자기 자신을 제외한 3의 배수를 모두 지운다.

6) 남아있는 수 가운데 5는 소수이므로 오른쪽에 쓴다.

7) 자기 자신을 제외한 5의 배수를 모두 지운다.

8) 남아있는 수 가운데 7은 소수이므로 오른쪽에 쓴다.

9) 자기 자신을 제외한 7의 배수를 모두 지운다.

10) 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.