[프로그래머스] 소수찾기 - Math.sqrt(n), Set.size()

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

 

n까지의 숫자들 중 소수갯수 찾기

 

첫번째 방법

나름 머리 쓴다고 소수를 찾으면 그 수의 배수를 제거해줬다.

function solution(n) {
    var answer = 0;
    const isPrime = new Array(n).fill(true);
    
    for(let i = 2; i <= n; i++) {
        // 소수찾음
        if (isPrime[i-1]) {
            answer++;
            
            for (let multiple = i*2; multiple <= n; multiple += i) {
                // 소수의 배수 제거
                if (multiple % i === 0) {
                    isPrime[multiple-1] = false;
                }
            }
        }
    }
    return answer;
}

 

 

두번째 방법

• 소수는 2를 제외하고 다 홀수이다
• 2는 소수이다, 1은 아니다.
• 제곱근까지만 (<=) 확인한다. 왜?
  • a * b = n이라고 하면, 약수인 a,b 중 하나는 무조건 sqrt(n)보다 작거나 같으므로, sqrt(n)까지만 확인하면 더 효율적이다.
• Set.add, delete, size

function solution(n) {
    const s = new Set();
    for(let i=3; i<=n; i+=2){ // 소수는 2빼고 홀수임, 1은 소수아님
        s.add(i);
    }
    s.add(2); // 2는 소수다
    
    // 홀수 중에서 홀수의 배수 제거하기
    const sqrt = Math.floor(Math.sqrt(n)); // Math.sqrt(n)
    for(let j=3; j <= sqrt; j++){ 
        if(s.has(j)){
             for(let k=j*2; k<=n; k+=j){ 
                s.delete(k);
             }
        }
    }
    return s.size;
}