125. 소수 찾기 Javascript

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

 

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하라
• 주어진 자료는 무엇인가?
   - 1부터 입력받은 숫자 n
• 조건은 무엇인가?
   - n은 2이상 1000000이하의 자연수

2. 계획

1. 소수 판별하는 함수를 만든다
2. 1부터 n을 소수 판별하는 함수에서 소수인지 아닌지 확인하고 소수라면 count+1한다.

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

첫번째 풀이

const solution = (n) => {
  const set = new Set();
  for (i = 2; i <= n; i++) {
    set.add(i);
  }

  for (i = 2; i <= Math.sqrt(n); i++) {
    if (set.has(i)) {
      for (j = i * 2; j <= n; j += i) {
        set.delete(j)
      }
    }
  }

  return set.size
}

test('findPrime', () => {
  expect(solution(10)).toEqual(4);
  expect(solution(5)).toEqual(3);
});

 

 

두번째 풀이

const isPrime = () => {
  for (j = 2; j <= Math.sqrt(i); j++) {
     if (i % j === 0) {
       return false
     }
   }
   return true
}

 const solution = (n) => {
   let count = 0;
   for (i = 2; i <= n; i++) {
     if (isPrime(i) === true) {
       count++
     }
   }
   return count;
 }

4. 반성

• 처음에 두번째 풀이로 풀었는데 효율성에서 계속 시간 초과가 났다. 그래서 에라토스테네스의 체를 사용해야겠다 생각했다. 
• set을 사용해서 2부터 해당 수의 배수를 삭제했다. 배열과는 삭제 시 달리 O(1)이 걸린다.  이렇게 효율성까지 통과했다.
• 두번째 풀이를 다시 시도해봤다. 처음에는 소수 구하는 함수를 나눠서 하지 않았었는데 이번에는 함수를 따로 빼서 해봤다. 
• 함수를 쪼개니 효율성이 통과가 되었다.