[JS] 소수찾기

https://programmers.co.kr/learn/courses/30/lessons/12921?language=javascript

프로그래머스

Question

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

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

 

제한조건

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

입출력 예

n	return
10	4
5	3

 

---

Solution

1부터 n까지의 숫자 중 소수를 모두 찾아야할 경우엔 에라토스테네스의 체를 쓰는 것이 가장 효율적이다.

하지만 비교를 하기 위해 다른 알고리즘도 이용해 보겠다.

 

1. 단순 루프로 풀기

2부터 n까지 루프를 돌려 찾기

// O(n)
function isPrime(num) {
  for(let i = 2; i < num; i++) {
    if (num % i === 0) {
      return false;
    }
  }
  return true;
}

function solution(n) {
  let answer = 0;
  for(let i = 2; i <= n; i++) {
    if (isPrime(i)) {
      answer += 1;
    }
  }
  
  return answer;
}

이 경우는 성능이 매우 느리기 때문에 모든 케이스를 통과하지 못한다.

 

2. 제곱근까지만 루프 돌리기

소수는 그 소수의 제곱근 위로의 수로는 나눠지지 않으므로 2부터 n의 제곱근까지만 루프를 돌려준다.

// O(sqrt(n))
function isPrime(num) {
  for(let i = 2; i * i <= num; i++) {
    if(num % i === 0) {
      return false;
    }
  }
  return true;
}

function solution(n) {
  let answer = 0;
  for(let i = 2; i <= n; i++) {
    if (isPrime(i)) {
      answer += 1;
    }
  }
  
  return answer;
}

정확성 테스트는 시간초과 없이 모두 통과하지만 효율성 테스트에서 모두 실패한다.

 

 

3. 에라토스테네스의 체

// O(n log n)
function getPrimes(num) {
  const primeArr = [false, false, ...Array(num - 1).fill(true)];
  
  for(let i = 2; i * i <= num; i++) {
    if (primeArr[i]) {
      for(let j = i * 2; j <= num; j += i) {
        primeArr[j] = false;
      }
    }
  }
  
  return prime.filter(Boolean);
}

function solution(n) {
  return getPrimes(n).length;
}