[js] 소수 찾기 방법 (width 프로그래머스)

JS에서 소수 찾는 방법 몇 가지를 난이도 별로 정리해보았다. 프로그래머스를 풀다 보면 소수와 관련된 문제들이 많은데 자꾸 까먹고 그래서한번 정리해보겠다. 

 

 

소수  = 1과 자기 자신으로만 나누어지는 수를 의미합니다. ( 1은 소수가 아닙니다 !)

 

 

# 관련 프로그래머스 

LV01: 소수 찾기 

LV02: 소수 찾기

 

 

[ Basic ] 소수 찾기 

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

function solution (n) {
	let count = 0;
    
    for( let i = 2; i <= n; i++ ){
    	if( isPrime(i)) {
        	count++;
        }
    };
    
    return answer;
}

 

* solution(10)

 

 

[ LV01 ] 소수 찾기 

 

조금 더 깊게 효율성을 고려해보자면, << 에라토스테네스의 체 >> 를 사용할 수 있습니다. 

function solution(n) {
    let arr = new Array(n - 1).fill(2).map((ele, idx) => ele += idx);

    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === 0) continue;
        
        for (let j = i + arr[i]; j <= n; j += arr[i]) {
            arr[j] = 0;
        }
    }
    
    return arr.filter(ele => ele).length
}

 

 

 

혹은 << set >> 을 사용해서 푸는 방법도 있습니다. 배열은 시간 초과가 나지만 이를 set 을 통해서 해결한 것입니다. 결국은 이 방법 또한 에라토스테네스의 체를 사용한 방법이죠. 

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

 

 

 

[ LV02 ] 소수 찾기 (아직 미 시도)