[Programmers] Lv1. 소수 찾기 (JavaScript)

문제

 

 

---

 

 

풀이

1차 : (정확성 75점 / 효율성 0점) 오답

function solution(n) {
    let arr = [];
    let answer = 1;
    
    if(n === 2) {
        return 1;       
    } else {
        for(let i = 3; i <= n; i += 2) {
            arr.push(i);
        }
        
        for(let j = 0; j < arr.length; j++) {
            let cnt = 0;
            for(let k = 1; k <= Math.sqrt(arr[j]); k++) {
                if(Number.isInteger(arr[j] / k)) {
                    cnt++;
                }
            }
            if(cnt < 2) {
                answer++;
            }
        }
        return answer;
    }
}

 

 

2차

코드2

function solution(n) {
    let arr = [];

    for(let i = 2; i <= n; i++) {
        arr[i] = i;
    }

    for(let i = 2; i <= n; i++) {
        if(arr[i] === 0) {
        	continue;
        }

        for(let j = i*2; j <= n; j += i) {
            arr[j] = 0;
        }
    }

    return arr.filter(v => v !== 0).length;
}

 

 

---

 

리뷰

• 효율성에 대한 고려 필요 (실행 복잡도 고려)