[프로그래머스] 소수 찾기 자바스크립트 feat. 에라토스테네스의 체 이해하기

드엔트론프·2022년 9월 28일

소수찾기 알고리즘 에라토스테네스의체 자바스크립트 프로그래머스

알고리즘

목록 보기

2/5

문제 설명

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 getPrimes(input) {
  // 모든 값에 true가 들어있는 배열을 하나 생성한다.
  const numsArr = Array.from({ length: input + 1 }, () => true);

  // 소수를 담을 빈 배열을 정의해준다.
  const primeNumbers = [];

  /*
  정의한 numsArr[2] 부터 반복문을 돈다.
  0과 1은 확실히 소수가 아니기 때문!
  */
  for (let i = 2; i <= input; i++) {
    // 만약 numsArr[i]번째 값이 true라면,
    if (numsArr[i]) {
      // primeNumbers배열에 값 i를 push 해준다.
      primeNumbers.push(i);

      
      //인덱스가 i의 배수인 'numsArr'의 모든 요소를 false로 변환해준다.
      //이 for문이 헷갈릴 수 있다. 집중!
      for (let j = i + i; j <= input; j += i) {
        numsArr[j] = false;
      }
    }
  }
  
  return primeNumbers.length;
}

console.log(getPrimes(10)); // 4

해설 📝

앞서 소수문제들이 나올 때마다 곤욕을 치뤘다.
에라토스테네스의 체가 어떤 원리인지는 이해했으나, 코드가 왜 저렇게 짜여야 하는지를 이해 못해 거진 반나절을 시간을 쏟고 있었다.
결국 코드가 얘기하는건 에라토스테네스를 어떻게 구현했냐하는 방법을 보여주는 것인데,
사람마다 조금씩 다르게 하고, 그러다보니 자꾸 단순한 부분에서 막혔던 것이다.
찾다 찾다 결국 딱 내가 이해하기 쉬운 정도의 ? (어쩌면 하도 보다보니 순간 이해가 된 걸 수도 있겠다.)
코드 구현방법을 찾을 수 있었다.

조금 더 찬찬히 살펴보자.

배열 정의 부분이 이해가면 빠르게 지나가도 된다. 괜히 길게 썼다고 생각.

// 모든 값에 true가 들어있는 배열을 하나 생성한다.
const numsArr = Array.from({ length: input + 1 }, () => true);

Array객체 메소드중 하나인 Array.from 메소드는

Array.from(arrayLike[, mapFn[, thisArg]]) 다음과 같은 매개변수를 갖게 되는데,
어렵게 보지말고 다음 예제를 보면 감을 잡을 수 있다.

console.log(Array.from('foo'));
// expected output: Array ["f", "o", "o"]

console.log(Array.from([1, 2, 3], x => x + x));
// expected output: Array [2, 4, 6]

첫 번째 매개변수에 들어가는
arrayLike는 배열로 변환하고자 하는유사 배열 객체나 반복 가능한 객체
이다.
그래서 'foo' 만 넣어도 출력값은 ["f","o","o"] 가 나오는 걸 알 수 있다.

그 뒤 매개변수는 더 어렵게 써있지만,
간단히 말해 array의 고차함수인 map 함수가 붙었다고 보면 된다.
*mapFn, thisArg 는 옵션값이다.

new Array(n+1).fill 이 더 빠르다.

Array.from은 조금 굳이? 싶을 수 있다. 비교해보려 다른 방법을 찾았는데, 이렇게 정의하는 것이 훨씬 빨랐다.

//사실 이 정의가 더 알아보기 쉬운 듯 하다. n만큼의 길이 +1 배열에 true값을 넣는것이다.
let arr = new Array(input+1).fill(true);

Array 만드는것도 어려워! for문을 쓰자.

// 웃긴건 그냥 for문으로 만든 arr도 위에 잘 이해했다고 가져온 Array.from 보다 빠르다.
const numsArr = [];
for(let i = 0; i <= input ; i++){
  numsArr.push(true);
}

참고로 그냥 for문은 input+1이 아니다.
Array로 생성하면 그게 length여서 +1을 해준 것이다.
뭔 말이냐면, new Array(2) 하면 index 0과 1이 있는, length가 2인 배열을 생성한다.
for는 0부터 input을 포함하게 돌기 때문에 배열의 길이가 1 더 길게, 원하는대로 생성 된 것임

배열 하나 정의하는데 이렇게 길게 설명할 일인지...!
다음 중첩 for문을 한번에 살펴보자.

  for (let i = 2; i <= input; i++) {
    // 만약 numsArr[i]번째 값이 true라면,
    if (numsArr[i]) {
      // primeNumbers배열에 값 i를 push 해준다.
      primeNumbers.push(i);

      //인덱스가 i의 배수인 'numsArr'의 모든 요소를 false로 변환해준다.
      //이 for문이 헷갈릴 수 있다. 집중!
      for (let j = i + i; j <= input; j += i) {
        numsArr[j] = false;
      }
    }
  }

i가 2부터 시작하는건 위에서도 말했지만, 배열의 0번째, 1번째인 0과 1은 당연하게도 소수가 아니기 때문에 바로 2부터 시작하는 것이다.

input 값이 10이라고 가정하고 for문을 돌아보자.

numsArr[2] 는 true이다. for(let i =2; i <= 10; i++)
primeNumbers에 2를 넣어준다. // primeNumbers = [2]
중첩된 for(let j = 4; j <= 10; j= j+i)
3-1. numsArr[4] = false; 로 바꾼다.
3-2. numsArr[6] = false; 로 바꾼다.
3-3. numsArr[8] = false; 로 바꾼다.
3-4. numsArr[10] = false; 로 바꾼다.
numsArr[3] 는 true이다. for(let i =3; i <= 10; i++)
primeNumbers에 3를 넣어준다. // primeNumbers = [2, 3]
중첩된 for(let j = 6; j <= 10; j= j+i)
6-1. numsArr[6] = false; 로 바꾼다. -> 이미 false긴 하다.
6-2. numsArr[9] = false; 로 바꾼다.
numsArr[4] 는 false다. (3-1에서 처리됨)
numsArr[5] 는 true이다. for(let i =5; i <= 10; i++)
primeNumbers에 5를 넣어준다. // primeNumbers = [2, 3, 5]
중첩된 for(let j = 10; j <= 10; j= j+i)
10-1. numsArr[10] = false; 로 바꾼다. -> 이미 false긴 하다.
numsArr[6] 는 false다. (3-2에서 처리됨)
numsArr[7] 는 true이다. for(let i =7; i <= 10; i++)
primeNumbers에 7을 넣어준다. // primeNumbers = [2, 3, 5, 7]
중첩 for문의 조건을 벗어난다. for(let j = 14; j <= 10; j= j+i)
numsArr[8] 는 false다. (3-3에서 처리됨)
numsArr[9] 는 false다. (6-2에서 처리됨)
numsArr[10] 는 false다. (6-2에서 처리됨)

for문을 순서대로 따라가면 이런 식이다.
이게 참 뭐가 어려웠는지 계속 막혔었다.

다 이해했다면 여러분은 소수찾기의 기본이 된 것이다 👏

더 개선하기 ↑↑↑

이 코드, 잘 작동한다. 그런데 한 가지 문제가 있다.
7, 11, 15, 16, 17번을 보면, 이미 false인데도 불구하고 for문은 계속해서 도는 것이다.
(하지만 사실 위 코드로도 이번 문제는 통과가 가능하다는 점)

그렇다면 어떻게 하는 게 좋을까?
제곱근을 활용하면 된다.

제곱근

64라는 숫자로 예를 들어보자.
64를 n * m 으로 나누었을 때,

n	m
1	64
2	32
4	16
8	8
16	4
32	2
64	1

8 X 8 이후 똑같은 게 보인다.
그 말은 즉, 64의 제곱근인 8까지만 체크해도 소수가 아닌 배수를 걸러낼 수 있다는 말이다.

제곱근을 사용한 코드 √

  function solution(input) {
   let numsArr = new Array(input+1).fill(true);
   const primeNumbers = [];
   numsArr[0] = false;
   numsArr[1] = false;
    
   for (let i = 2; i <= Math.floor(Math.sqrt(input)); i++){
    if (numsArr[i]) {
      for (let j = i + i; j <= input; j += i) {
        numsArr[j] = false;
      }
    }
  }
  for(let i = 0; i < numsArr.length; i++){
     if(numsArr[i]){
         primeNumbers.push(i)
     }
 }
  return primeNumbers.length;
}

이게 개선했다고 한 것이긴 한데, 중첩 for문에 추가로 for문이 또 쓰여서 막상 돌려보면 크게 시간차이가 나지 않는 듯 하다. 큰 숫자로 비교하지 않아서 그럴수도 있겠다.

reduce로 출력하기 👀

마지막 for문으로 primeNumber 출력하는 것을 reduce로 출력하는데, 이게 더 이해하기 어려울 수 있어 따로 적는다.

function solution(input) {
  // let numsArr = new Array(input+1).fill(true);
    // const primeNumbers = [];
    const numsArr = [];
    for(let i = 0; i <= input ; i++){
        numsArr.push(true)};  
  numsArr[0] = false;
  numsArr[1] = false;
    
  for (let i = 2; i <= Math.floor(Math.sqrt(input)); i++) {
    if (numsArr[i]) {
      for (let j = i + i; j <= input; j += i) {
        numsArr[j] = false;
      }
    }
  }
 const primeNumbers = numsArr.reduce(
    (result, element, index) =>
      element ? (result.push(index), result) : result,
    []
  );
  return primeNumbers.length;
}