2022.01.26(Wed.) <자바스크립트에서 소수 구하기>

소수가...뭐였더라...?

1. 문제의 발단

다시 알고리즘 공부를 시작하고 나서 프로그래머스를 풀고 있었다. 레벨 1 문제가 얼마 안 남았는데, 왠지 남은 문제가 소수 관련 문제뿐인 것이다...! 이대로는 안 되겠다 싶어서 소수에 대한 공부를 따로 해 보려고 한다.

2. 소수?

• 1과 자기 자신 이외에 숫자로 나누어 떨어지지 않는 숫자

3. 반복문 사용하기

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

• 소수인지 아닌지를 판별 할 수 있다. 설명할 필요 없이 간단하다.

4.  Math.floor과 Math.sqrt를 사용하기

function isPrime(num) {
	if(num < 2) return false;
	// 자연수 인지를 판단한다.
    
	for(let i = 2; i <= Math.floor(Math.sqrt(num)); i++){
    	if(num % i === 0){
      		return false; 
    	}
  	}
  return true;
}

• Math.floor() : 소수점이 있는 숫자를 내림한다.
• Math.sqrt() : 제곱근을 반환한다.
• 즉, num의 제곱근을 받아 내림하여 소수점을 때 준 후에 숫자를 최대 숫자로 보고 나머지는 위의 방법과 거의 동일하다.

5. 에라토스테네스의 체

function isPrime(n) {
	// 먼저 0 부터 n 까지 true로 이루어진 배열을 만들어 준다. 이들이 모두 소수라고 친다.
    // 하지만 0과 1은 소수에서 제외한다.
    let arr = new Array(n + 1).fill(true).fill(false, 0, 2);
    
    // 소수들이 들어갈 배열을 2부터 제곱 보다 작을경우에 돈다.
    for(let i = 2; i * i <= n; i++) {
    	// 이때, arr[i]에 해당하는 숫자가 true 즉, 소수라면
        if(arr[i]) {
        	// 그 소수의 제곱부터 n까지의 모든 제곱근들을 다 false로 소수가 아니라고 표시한다.
            for(let j = i * i; j <= n; j += i) {
                arr[j] = false;
            }
        }
    }
    // 소수 표시가 끝나면 filter로 소수, 즉 true인 요소의 length를 반환한다.
    return arr.filter(el => el === true).length;
}

• 간단하게 말하면 정해진 범위 내의 소수들의 배수를 싹 다 제외하면 소수만 남는다.
• 예를 들어, 1 ~ 25까지의 소수의 개수를 구하려고 할 때, 1을 제외한 2부터 25의 제곱근인 5까지의 소수들을 구한다. 그러면 소수는 2와 3뿐이다. 이때 2의 배수인 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24를 제외하고, 3의 배수인 3, 6, 9, 12, 15, 18, 21, 24를 제외한다. 하지만 2와 3은 n의 제곱근인 5의 소수이기도 하였기 때문에 제외하고, 2, 3, 5, 7, 11, 13, 17, 19, 23이 남는다.
• 그러므로, 소수의 갯수를 구할 때 더 유리하다. 소수인지를 판별할 때는 다른 방법이 더 빠를 수 있다.
• 소수 자체를 구하려면 result에 true인 요소들의 index 번호를 얻으면 된다.