[코딩테스트] 프로그래머스 소수찾기 자바스크립트

어렵다..

내가 푼 답은 테스트 10번부터, 효율성 테스트는 통과를 못했다..╥﹏╥

 

일단 이 문제에서 알아야 할 것.

1과 자신을 제외한 값으로 나누었을 때 
나머지가 0인 값이 1개라도 나오면 소수가 아니다.

< 에라토스테네스의 체 >
일종의 노가다 방식이라 상당히 무식한 방법이긴 하지만, 특정 범위가 주어지고 그 범위 내의 모든 소수를 찾아야 하는 경우, 아직까지 소수들 간의 연관성(=소수를 생성할 수 있는 공식)이 나오지 않았으므로 에라토스테네스의 체보다 빠른 방법이 없다. 프로그래밍에도 수학적 지식이 필요하다는 걸 일깨워주는 좋은 예시.

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

에라토스테네스의 체 - 나무위키

< 제곱근(sqrt) 범위 나누기 기법 >
제곱근을 기준으로
그 곱은 대칭적으로 곱이 일어나므로
제곱근 이하의 작은 값까지만 검사를 하면
나머지는 검사를 할 필요가 없다는 방법을 의미

 

가장 중요한 것은 < 에라토스테네스의 체 > 이 개념을 모르면 효율성 검사에서 통과하지 못한다...

---

📌 문제설명

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를 반환

---

📌 문제풀이

1. 내 풀이 : 효율성 테스트 통과X

function solution(n) {
    let answer = 0;
    let notAnswer = 0;
    for(let i=2; i<=n; i++){
        for(let j=1; j<=i; j++){
            if(i % j === 0) notAnswer++
        }
        if(notAnswer===2) {answer++} 
        notAnswer = 0 //초기화!!!
    } 
    return answer
}

2. 내 풀이 : 효율성 테스트 통과X

function solution(n) {
    let arr = [];
    for(let i=2; i<n+1; i++){
        for(let j=1; j<i+1; j++){
            if(i % j === 0) arr.push(i)
        }
    } 
    
    let answer = [];
    for (let i=0; i<n+1; i++) {
        if(arr.filter(num=> num === i).length === 2){answer.push(i)}
    }

    return answer.length
}

3. 누군가의 풀이 : 제곱근(sqrt) 범위 나누기 기법, 효율성 테스트 통과X

// 소수인지 판별하는 함수
function isPrime(x) {
  for (let i = 2; i <= Math.sqrt(x); i++) {
    if (x % i === 0) return false;
  }
  return true;
}

function solution(n) {
  // 소수의 개수를 저장할 변수
  let answer = 0;
  // 1은 소수가 아니므로 2부터 n까지 모든 수에 대해
  for (let i = 2; i <= n; i++) {
    // 소수이면 소수의 개수에 1 추가
    if (isPrime(i)) answer++;
  }
  return answer;
}

4. 누군가의 풀이 : 에라토스테네스의 체, 효율성 테스트 통과O

function solution(n) {
  // 2부터 n까지의 수로 구성된 Set
  const s = new Set();
  for (let i = 2; i <= n; i++) {
    s.add(i);
  }

  // 2부터 n의 제곱근보다 작은 최대 정수까지 
  for (let j = 2; j < Math.sqrt(n); j++) {
    // Set에 해당 수가 포함되면
    if (s.has(j)) {
      // 그 수를 제외하고 그 수의 배수는 모두 삭제
      for (let k = j * 2; k <= n; k += j) {
        s.delete(k);
      }
    }
  }
  return s.size;
}

4. 누군가의 풀이 : 에라토스테네스의 체, 효율성 테스트 통과O

function solution(n) {
    // 소수 리스트 담을 배열 생성
    let arr = [];
    
    // 0과 1을 제외한 2부터 n까지 배열에 담아줍니다.
    for(let i=2; i<=n; i++) {
        arr[i] = i;
    }
    
    for(let i=2; i<=n; i++) {
    	// 인덱스 2부터 반복문 돌면서 0이면 다시 다음 반복문을 돕니다.
        if(arr[i]===0) continue;
        
        // 각 인덱스(i)의 배수들을 0으로 지정해줍니다.
        for(let j=i*2; j<=n; j+=i) {
            arr[j] = 0;
        }
    }
    
    // filter를 이용해 0이아닌 수들의 개수를 return합니다.
    return arr.filter(v => v!==0).length;
}