코딩테스트연습 > 연습문제 > 소수찾기

풀이

첫번째 시도 시간초과로 실패했다

짝수 홀수로만 나눴는데 이정도로는 부족한가보다. 그래서 소수의 배수를 아얘 제외해야겠다는 생각을 했다.

짝수 홀수도 애초에 소수인 2로 나눈것이기 때문에 똑같은 원리를 좀 더 효율적으로 쓰겠다는 것이다.

function solution(n) {
    let answer = 1;
    const pri=(num)=>{
        for(let i=3;i<num;i=i+2){
            if(num%i===0){
                return;
            }
        }
        return answer++;
    }
    for(let i=3;i<=n;i=i+2){
        pri(i)
    }
    return answer;
}

올바른 풀이

function solution(n) {
    let answer = 0;
    let arr = [];
    for(let i=2;i<=n;i++){
        arr[i]=1;
    }
    
    for(let i=2;i<=n;i++){
        if(arr[i]===0);
        else{
            for(let j=i*2;j<=n;j+=i){
                arr[j]=0;
            }
        }
    }
    
    for (let i=2;i<=n;i++) {
        if (arr[i]!==0){
            answer++;
        }
    }
    
    return answer;
}