[Algorithm] 소수찾기 (에라토스테네스의 체)

코딩테스트의 정말 큰 문제점이 뭐냐면, 했던 걸 계속 까먹는다는거다. 내가 짱구를 굴려서 풀었으면 그 이후에 풀 때도 짱구를 굴려서 풀 수 있을건데, 도저히 솔루션을 못찾겠어서 타인의 정답을 참고하게 되면 이런 문제가 생긴다.

그 이유가 뭐냐면, 실제로 사용되는 수학적 개념들을 요구하는 문제가 있기 때문인데 이 대표적인 예가 최대공약수, 최소공배수찾기, 에라토스테네스의 체를 활용해 소수찾기 같은 문제들이 그렇다. 

앞선 게시물에서 이 내용들을 언급했음에도 또 내가 이걸 작성하는 이유는 내가 저것들을 봤음에도 불구하고 까먹었기 때문이다. ㅎㅎ.. 사실 앞선 게시물에서는 제대로 이해했다기보단 솔루션 저장소같은 느낌으로 모르겠으면 또 보려고 쓴거라, 이번엔 제대로 이해한 내용 그대로 작성해볼 예정이다. 

 

1. 소수 (Prime Number) 는 무엇인가?

어떤 수의 약수들이 자기 자신, 그리고 1 이렇게 둘만 있는 경우를 소수라고 부른다. 

솔직히 이 소수 구하는 방법 자체는 되게 쉽다. 그냥 2부터 자기 자신까지의 모든 수로 자기 자신을 나눠보고, 자기 자신을 제외하고 모두 다 나눠떨어지지 않는다면, 그건 소수임.

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

console.log(solution(13)); // true

이렇게 말이다. 

 

2. 소수를 찾는데 사용되는 법칙

사실 상 위의 방식으로 찾아도 아무런 문제가 없지만 이는 상당히 효율성면에서 구린 방법이다.

그래서 일반적으로 코딩테스트에서는 실제 수학적으로 사용되는 법칙들을 많이 적용하는 편인데 소수 찾는거에도 당연히 있다. 그게 "에라토스테네스의 체" 임.. 이것도 알고리즘이라고 부르긴하더라. 

기본 전제 : 1 이상의 자연수는 따지고 보면 모두 소수들의 곱으로 이뤄져있다. 
방법 : 2부터 소수인지 판별하고자 하는 수의 제곱근까지 소수의 배수들만 제외시키면 남는 수들이 모두 소수이다.

이렇게 각 소수들의 배수들을 모두 걸러내기 때문에 체라는 이름이 붙은 것 같음.

이걸 적용시키는 코드를 한번 보자. 

function solution(n){
    let arr = Array(n + 1).fill(true).fill(false, 0, 2);
    for(let i = 2 ; i * i <= n; i++){
        if(arr[i]){
            for(let j = i * i; j <= n; j+=i){
                arr[j] = false;
            }
        }
    }

    return arr;
}

이런 식으로 구현을 하게 되면, 소수들의 배수들을 모두 싹다 false로 처리 해둠으로 인해서 false일 경우 작업을 스킵도 할 수 있고, 마지막에 true인 수들만 세면 되기 때문에 앞서서 써둔 소수 판단 함수를 쓰는거보다는 훨씬 효율적이라고 볼 수 있다.

 

 

이 다음엔 최대공약수, 최소공배수 구하는 거 한번 알아보도록 하겠다.