🧑‍💻 내 풀이 (두번째)

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

• 이번엔 배열을 사용 안하니 테스트 10은 통과 했지만 11, 12를 통과 못함. 내 풀이가 O(n²) 이라 그런것이라 추정
• 이전의 입력값들을 기억하는 메모이즈 형태로 만들어보려 했으나 문제의 의도와 동떨어진것 같다고 생각
  
  
  

🧑‍💻 내 풀이 (세번째 2022.06.03)

• 어떤 분이 써놓으신 효율성 테스트를 위한 조언이 큰 도움이 됨
  

풀이 1

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

• 소수를 2/num 까지만 검색해서 좀더 단계를 줄였으나 그래도 o(n²)이라 여전히 느린편
  
  
  

풀이 2

function solution(n) {
    let count = 0;
    
    function isPrime(num) {
        if (num === 1) return false;
        
        for (let i = 2; i * i <= num; i++) {
            if (num % i === 0) return false;
        }
        
        return true;
    }
    
    for (let i = 2; i <= n; i++) {
        if (isPrime(i)) count++;
    }
    
    return count;
}

• 실제로 합성수를 나누게 되는 몫과 나머지는 반드시 둘중 하나가 √n 이하라는 수학적 개념을 이용하여 o(n√n) 까지 끌어올리니 통과됨
• 참고
  
  
  

풀이 3

function solution(n) {
    let count = 1;
    
    function isPrime(num) {
        if (num === 2) {
            return true;
        } else if (num % 2 === 0) {
            return false;
        }
        
        for (let i = 3; i * i <= num; i += 2) {
            if (num % i === 0) return false;
        }
        
        return true;
    }
    
    for (let i = 3; i <= n; i += 2) {
        if (isPrime(i)) count++;
    }
    
    return count;
}

• 소수는 2 이외에는 전부 짝수니 2는 따로 케이스를 나눠주고 3부터 2씩 더해가며 홀수만 소수인지 판단함
• 시간복잡도는 상수가 무시되므로 풀이2와 동일한 O(N√N) 이지만 실제로는 풀이2에 비해 단계가 반으로 줄어들은것
  
  
  

🧑‍🏫 다른사람들 풀이 참고

풀이 1

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;
}

• 유일한 수만 담을 수 있는 set 객체와 에라토스테네스의 체를 활용하심