JavaScript - 소수구하기 (에라토스테네스의 체)

 

 

 

소수는 자기 자신과 1 로만 나뉘어지는 수이다.

예를 들어 5 는 1 로만 나뉘어 질 수 있다.

 

자, 소수를 구하는 판별식을 정리해보았다. 이제 당신은 이걸 가지고 응용하기만 하면 된다 :)

JavaScript 에서 소수인지 검사하기 위해서는,
For 문으로 검사를 할 때, {
  number 이 0, 1 이면 탈락                                         → 1은 소수가 아님
  number 가 2 이면 소수이다                                      → 2은 소수이다
  number % index === 0 이라는 조건에 들거든 탈락 → 자기자신과 1로만 나뉘어져야 된다는 소수의 조건 성립이 X)
}

 

 

 

방법 1)  반복문 함수 판별식 

함수는 보기에 너무 간단하다. 하나하나씩 다 돌려서 소수에 부합하는 것을 찾아낸다.

시간복잡도는 O(N) 으로 무난하지만, 해당하지 않는 숫자까지 일일히 하나하나 검사해야 한다는 단점이 있다.

function isPrime(num){
  if(num < 2) return false;   // 0, 1 은 소수가 아니다.
  if(num === 2) return true;  // 2 는 소수이다

  for(let i=2; i < num; i++){ // 2 이상의 수들로 하나하나 나누어 본다
    if(num % i === 0)  	      // 하나라도 나머지 없이 깨끗하게 나뉜다면
      return false;           // 소수가 아니다 탈락!
    }
  }
  return true;	  	      // 이 관문을 무사히 거친 녀석이라면 통과!
}

 

 

 

 

방법 2) 에라토스테네스의 체

쉽게 말해 n 까지의 수에서 소수 만을 쏙쏙 골라내는 알고리즘이다.

요 방법의 시간복잡도는 O(N log(logN)) 이다. 

 

예를 들어 100 까지의 수가 있으면 빙고판 지우듯 2의 배수를 다 지워버린다. 3의 배수도 4의 배수도..

대신 2 나 3, 4 등의 (본인)은 스스로 지우지 않는다. (물론 4는 2의 배수이므로 자연스럽게 지워지겠지만 말이다)

이런 식으로 배수를 지우다 보면 남는 최후의 숫자들이 소수이다.

출처 : 위키

 

그럼 코드로 구현해보자. 하지만 잘 이해가 안가는 부분이 있어서 공부하면서 정리해보았다. 

let n = 5;    // 5 안에 들어있는 소수를 알고 싶다고 치자 
let arr = []; // boolean 값이 들어갈 arr 를 선언

// 1. arr 만들기 (소수만 true 로 표기할거다)
Array.from({length: n + 1}, (_,i) => {  // length는 n + 1 이다. 쓸모없는 인덱스 0을 포함시킬거다
					// 아래쪽 for문 돌릴 때 인덱스 order가 필요하기 떄문이다
    if(i <= 2){ 			// 인덱스0 이랑 인덱스1은 소수가 아니므로,
        arr.push(false); 		// false 를 넣어주자
    } else {
        arr.push(true);
    }
})

// 2. 위 코드를 실행해보면 결과는 요렇게 나온다 
// [false, false, true, true, true, true]

// 3. i의 배수 솎아내기 (배수들을 false 로 만들자)
for(let i = 2; i*i <= n; i++){		  // i=2 일때, i*i=4 이라, i=2 일때만 i*i <= n을 만족한다
	    				  // (즉, 5 은 2 의 배수만 포함한다는 말이다)
    if(arr[i]){			  	  // arr[2] = true (소수)니까 무난히 if문 안으로 들어간다
        for(let j = i*i; j <= n; j += i){ // 이중 for문에서 j=4이고 for문 실행조건을 만족한다
            arr[j] = false;		  // 이제 arr[4] = false 로 바꿔주자 이렇게 
        }
    }
}

// 4. 위 코드를 실행해보면 결과는 요렇게 나온다
	      1    *2*	 *3*     4   *5*
// [false, false, true, true, false, true]
// 2, 3, 5 가 소수이다