Algorithm | 소수찾기 (에라토스테네스의 체)

문제 설명

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

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

제한 조건

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

예시

n	result
10	4
5	3

📍1차 시도

function solution(n){
  let primeNum = 0;
  for(let i=2; i<=n; i++){
    let zeroRemainder =0;
    for(let j=1; j<=i; j++){
      if(i%j===0){
        zeroRemainder++;
      }
    }
    if(zeroRemainder === 2){
      primeNum++;
    }
  }
  return primeNum;
}

몇번의 시도 후에 구글링을 통해서 "에라토스테네스의 체" 라는 소수 판별 법을 통해서 해당 알고리즘을 푸는 방법을 찾았다.

📍소수 판별 법 (에라토스테네스의 체)

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

에라토스테네스의 체 -> 풀이 point❗️

아래의 그림의 경우, 11^2 > 120 이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

⇒ n의 제곱근 보다 작은 수의 배수들만 지워주어 풀이한다.

참고자료 | 에라토스테네스의 체
참고자료 | velog - 프로그래머스 Lv1. 소수 찾기

📍2차 시도

function solution(n){
  let numbers = [];
  for(let i=0; i<=n; i++){
    numbers.push(i)
  }
  for(let j=2; j<=Math.sqrt(n); j++){
    for(let k=j; j*k<=n; k++){
      numbers[j*k] = 0;
    }
  }
  return numbers.filter(num => num !== 0).length-1 
  // 0과 1을 제외해야하지만 0은 filter에 의해 제외되므로 "1"을 전체 길이에서 제외하기 위해서 -1
}

풀이를 완료한 후 다시 보니 굳이 numbers배열을 for문을 돌려서 각 인덱스에 해당하는 숫자를 일일이 넣을 필요가 없다.⬇

📍2차 시도 (점검)

function solution(n){
  let numbers = Array(n+1).fill(1); // 📍0~n 인덱스 까지 모두 1로 채움
  for(let j=2; j<=Math.sqrt(n); j++){
    for(let k=j; j*k<=n; k++){
      numbers[j*k] = 0;
    }
  }
  return numbers.filter(num => num !== 0).length-2
}

효율성 테스트 에서는 확실히 더 나아졌다.

📍 Set을 이용한 다른 풀이

function solution(n) {
    const s = new Set();
    for(let i=1; i<=n; i+=2){
        s.add(i);
    }
    s.delete(1);
    s.add(2);
    for(let j=3; j<Math.sqrt(n); j++){
        if(s.has(j)){
             for(let k=j*2; k<=n; k+=j){    
                s.delete(k);
             }
        }
    }
    return s.size;
}

※ from 함수 ⇒ fill함수 처럼 사용하기 ※

function solution(n) {
    
    let sosu = Array.from({length : n+1}, v => true);
    
    for(var num = 2; num<=Math.sqrt(n); num++){
        if(sosu[num]){
            for(var i=num*num; i<=n; i+=num){
                sosu[i] = false;
            }
        }
    }
    const result = sosu.filter(x => x == true);
    return result.length - 2 ;
}

- Array.from

Array.from() 메서드는 유사 배열 객체(array-like object)나반복 가능한 객체(iterable object)를 얕게 복사해새로운Array 객체를 만듭니다.

Array.from( arrayLike [, mapFn [, thisArg]])

• 매개변수

  • arrayLike
    배열로 변환하고자 하는유사 배열 객체나 반복 가능한 객체.

  • mapFn (Optional)
    배열의 모든 요소에 대해 호출할 맵핑 함수.

  • thisArg (Optional)
    mapFn 실행 시에 this로 사용할 값.

• 반환 값
  새로운 Array 인스턴스.