소수 찾기

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

코딩테스트 연습 - 소수 찾기

2가지를 알고 있어야 한다.

1. Prime Number는 Root로 자신을 쒸운값 이하로 2부터 순차적으로 나누어서 나누어 지면 Prime이 아니다. 반대로 끝까지 안나누어 지면 Prime이다.

    function isPrime(digit){
        let count = Math.floor(Math.sqrt(digit));
        
        for(let i = 2; i <= count; i++){
            if(arr[i]==1)
                if(digit%i == 0) return false;
        }
        return true;
    }

2. 한번 Prime으로 선정이 된 값의 배수는 모두 Prime이 아니다.

    for(let i = 2; i <= n; i++){
        if(arr[i] == -1){
            if(isPrime(i)){
                count++;
                arr[i] = 1;
                for(let j = i+i; j <= n;j+=i){
                    arr[j] = 0;
                }
            }
        }
    }

 

상기 내용을 합치면 된다.

function solution(n) {
    let arr = new Array(n+1).fill(-1);
    let count = 0;
    for(let i = 2; i <= n; i++){
        if(arr[i] == -1){
            if(isPrime(i)){
                count++;
                arr[i] = 1;
                for(let j = i+i; j <= n;j+=i){
                    arr[j] = 0;
                }
            }
        }
    }
        
    return count;
    
    function isPrime(digit){
        let count = Math.floor(Math.sqrt(digit));
        
        for(let i = 2; i <= count; i++){
            if(arr[i]==1)
                if(digit%i == 0) return false;
        }
        return true;
    }
}