[ 08.10 ] 나만의 소수판별 템플릿, 그리고 실패담. (feat. 프로그래머스 - 소수찾기)

앞의 알고리즘을 풀다가 문득
소수판별하는 간단한듯 하면섣 사람 짜증나게하는 함수식은 하나쯤 외워버려도 좋겠다는 생각을 했다.

1. 첫번째 방법

    // 2부터 비교하기 시작해서 나누어 떨어지는 수가 있으면 소수가 아니다
    // for 문 조건을 number/2 로 해도 되는 이유는 i > number/2 가 되면 몫이 절대 0이 될수 없기 때문!
    // number/2 까지만 비교해 보아도 소수 판별이 가능하다
  const isPrime = (num) => {
    for(let i = 2; i<num; i++){
      if(num % i === 0) return false;
    }
    return true;
  }

2. 두번째 방법

 const isPrime = (num) => {
    let results = false;
    if(num === 2){
      return true;
    }
    for(let i=2; i<=Math.floor(Math.sqrt(num)); i++){
      if(num % i === 0){
        results = false;
        break;
      }
      else{
        results = true;
      }
    }
    return results;
  }

3. 세번째 방법

function isPrime(num) {
  let isTrue = true
  if(num === 1){
    return false;
  }
  for(let i = 2; i< num; i++){
    if(num % i !== 0){
      isTrue
    }else{
      isTrue = false;
    }
  }
  return isTrue;
}

첫번째 방법 극호.
역시 간단한게 최고. 짜릿해.

하고 호기롭게 프로그래머스 소수찾기 문제를 풀러갔다.

문제

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부터 n까지 arr 라는 빈배열에 다 담고
그 배열안에 있는 수가 소수이면 그 소수만 뽑아내서 렝스를 반환하면되겠다

💥 문제 풀이 - 노 완벽

function solution(n) {
    
      const isPrime = (num) => {
    for(let i = 2; i<num; i++){
      if(num % i === 0 ) return false;
    }
    return true;
  }
    
    let arr = [];
    for(let i = 2; i<=n; i++){
        arr.push(i); // [2,3,4,5,6,7,8,9,10]
    }
    arr = arr.filter((el)=>{
        if(isPrime(el)) return el;
    })
    return arr.length;
}

오케 일단 테스트 통과했고요

잘나가다가 테스트 10,11,12 번에서 막힌다.
왠지 망삘의 스멜이 난다.

주먹이 울었다.
혹시 저 템플릿이 잘못되었나 하고 두번째 템플릿 발사..

싸늘하다.
또 실행초과다. 도대체 뭐가 문제인지 몰라서 결국에는 구글링해서 찾아봤다.
all pass 인 다음의 풀이.. 나갑니다..
또로록 .. ..

💥 맞는 풀이

function solution(n) {
    
    let arr = [];
    let cnt = 0;
    for (let i = 0; i < n + 1; i++) {
        arr.push(true);
    }

    for (let i = 2; i * i <= n; i++) {
        if (arr[i]) {
            for (let j = i * i; j <= n; j += i) {
                arr[j] = false;
            }
        }
    }
    arr.splice(0, 2, false, false);
    for(let i = 0; i <arr.length; i++) {
        if(arr[i]) cnt++;
    }

    return cnt++;
}

울러갑니다.. 안녀엉 ..