JS, 에라토스테네스의 체

소수찾기 문제를 할때 반복문으로 풀게되면 효율성 테스트에서 시간초과로 실패가 뜸

이런 경우 에라토스테네스의 체 방법을 사용하면 효율적으로 문제를 풀어 효율성 테스트를 통과할 수 있음

 

[ 에라토스테네스의 체 ]

https://junkim.netlify.app/posts/programmers0807

 

1부터 제외하고 2부터 N까지 자신을 제외하고 순차적으로 자신의 배수들을 지워가면 결국에는 소수들만 남는다는 원리

n까지가 아닌 √n까지만 검색해도 결과는 같음

 

▶ 에라토스테네스의 체 과정

1. 2부터 N까지 모든 정수를 적음
2. 아직 지우지 않은 수 중 가장 작은 수를 찾음(이것을 P라고 하고 이 수는 소수)
3. P를 지우고 아직 지우지 않은 P의 배수를 크기 순서대로 지움
4. 아직 모든 수를 지우지 않았다면 다시 2번 단계부터 반복

 

▶ 에라토스테네스의 체 코드

function solution(n) {
    let arr = new Array(n+1).fill(true).fill(false, 0, 2)	//0과 1은 소수가 아니므로
    
    for(let i=2; i*i<=n; i++){	//√n만 해도 됨
        if(arr[i]){
            for(let j=i*i; j<=n; j+=i) arr[j] = false	// 배수들은 소수가 아니므로 false
        }
    }
    
    return arr.filter(el => el).length	//소수인 true값만 남겨 길이 return
}

 

function solution(n) {
    let arr = new Array(n+1).fill(true)	// 소수는 true
    
    for(let i=2; i*i<=n; i++){	//
        if(arr[i]){	
            for(let j=i*i; j<=n; j+=i) arr[j] = false	// 배수들은 소수가 아니므로 false
        }
    }
    
    return arr.filter(el => el).length - 2	//0,1은 소수가 아니므로 제외
}