[백준] 1929: 소수 구하기 - JS (에라토스테네스의 체)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

  접근 방식

 

에라토스테네스의 체 알고리즘은 큰 범위 내에 있는 모든 소수를 빠르게 찾을 때 효율적이다.

기본 원리는 다음과 같다.

 

 - 2부터 원하는 숫자 N 까지의 모든 숫자를 나열한다.

 - 2는 소수이므로, 2의 배수를 모두 제거한다.

 - 다음 남아있는 숫자인 3의 배수를 모두 제거한다.

 - 다음 남아있는 숫자인 5의 배수를 모두 제거한다.

 - 다음 남아있는 숫자인 7의 배수를 모두 제거한다.

 - 다음 남아있는 숫자인 ... ...

 

이런 방식으로 N 까지 한다. 남아 있는 숫자들이 2 부터 N 까지의 소수이다.

 

그리고 다른 방식은 숫자 N을 2 부터 루트N 까지 나누어 보는 것이다.

 

이 두 방식의 차이점은 메모리 제한, 시간 복잡도 이다.

 

에라토스테네스의 체 알고리즘은 N 크기의 배열을 필요로 하여 많은 메모리를 사용한다.

범위 내의 모든 소수를 찾는 경우에는 에라토스테네스의 체가 훨씬 빠르며, 범위가 커지면 커질수록 그 차이가 더 크게 나타난다.

반면 루트 N의 방법은 속도는 조금 느리지만 추가적인 메모리를 거의 사용하지 않는다.

 

 

에라토스테네스의 체

 

시간 복잡도: O(N log log N)

메모리: O(N)

 

 

루트N 

 

시간 복잡도: O(루트 N)

메모리: O(1)

 

이 글에서는 두 가지 방식 모두를 다루려고 한다. 

 

 

  풀이

 

먼저 루트이다.

 

먼저 result의 기본값을 소수를 의미하는 false 로 정의한다. 그리고 for문으로 i를 2부터 루트i 까지 나누어 본다.

만약 나누어 떨어진다면 소수가 아니므로 result를 true로 바꾼다. 그럼 콘솔에 출력되지 않는다.

 

반면 나누어 떨어지지 않는다면 소수이므로 result의 값을 false로 놔두고 출력한다.

 

{
  const M = 1;
  const N = 16;
  
  for(let i = M; i <= N; i++){
    let result = false;
    for(let j = 2; j <= Math.ceil(Math.sqrt(i)); j++){
      if(i % j == 0){
        result = true;
        break;
      };
    };
    if(i == 2){result = false};
    if(i == 1){result = true};
    if(result == false){
      console.log(i)
      };
  }

}

 

 

다음은 에라토스테네스의 체 알고리즘을 적용한 코드이다. 

 

sqrt 메서드는 루트를 반환하는 메서드인데, 이 부분은 N/2 로 바꿔도 크게 문제될 건 없어보인다.

아래 이미지가 그 이유이다. 아래 결과가 루트로 한 것이고 위에 결과가 N/2인데, 솔직히 루트N 까지만 확인해도 충분하다.

 

 

{
  const M = 1;
  const N = 16;
  
  const data: boolean[] = new Array(N+1).fill(false);
	data[0] = true;
	data[1] = true;

  for(let i = 2; i <= Math.sqrt(N); i++){
		if(data[i] == true){continue};
		
		let j = i;
		while(j <= N){
			j = j + i;
			if(j > N){break};
			data[j] = true;
		};
  }

  for(let [index, value] of data.entries()){
		if(index >= M && index <= N){
			if(!value){
				console.log(index);
			}
		}
	}
  
}

 

 

루트 방식

 

메모리가 차이 나는 이유는 처음에는 에라토스테네스의 체의 가장 큰 특징인 데이터를 미리 정해두는 것을 적용했기 때문이다.

위 제출에서는 그 부분을 제거하고 본문에 작성한 코드를 넣었다.

 

 

 

 

에라토스테네스의 체

 

두 코드의 차이점은 for문의 조건을 루트N으로 하였느냐 N/2 로 하였느냐의 차이이다. 큰 차이는 없어보인다.