글 작성자: 망고좋아
반응형

 

🎯 소수 찾기

📁 문제 출처

 

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

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상

programmers.co.kr

 

💡 생각

  • 소수는 에라토스테네스의 체로 구해놓고 풀면 시간 복잡도를 줄일 수 있다.

 

자바스크립트 에라토스테네스의 체

function prime() {
    let n = 1000000;
    let arr = Array(n + 1).fill(true).fill(false, 0, 2);

    for (let i = 2; i < Number(n ** 0.5) + 1; i++) {
        if (arr[i]) {
            for (let j = i * i; j <= n; j += i) {
                arr[j] = false;
            }
        }
    }
    return arr;
}

 

🛠 나의 코드

function prime() {
    let n = 1000000;
    let arr = Array(n + 1).fill(true).fill(false, 0, 2);

    for (let i = 2; i < Number(n ** 0.5) + 1; i++) {
        if (arr[i]) {
            for (let j = i * i; j <= n; j += i) {
                arr[j] = false;
            }
        }
    }
    return arr;
}

    

function solution(n) {
    let ans = 0;
    let arr = prime();
    
    for(let i = 1; i <= n; i ++ ) {
        if (arr[i] === true) {
            ans += 1
        }
    }
    return ans;
}
반응형