[JavaScript] 자바스크립트 소수 판별하기(feat. 반복문, 에라토스네테스의 체)

🎯 자바스크립트 소수 구하기

• 자바스크립트에서 소수 구하는 방법을 알아보자.

 

📝 반복문

while문 사용

function isPrime(m) {
    let divisor = 2;

    while (n > divisor) { // n이 나누는 수보다 클 때까지
        if(n % divisor === 0) { // n과 나누는 수가 나누어 떨어지면 
            return false; // 소수가 아님!
        } else {
            divisor++; // 나누어 떨어지지 않는다면 나누는 수 1 증가
        }
    }

    return true; // while문이 종료되면 그 수는 소수!
}

 

for문 사용

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

 

제곱근 사용

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

• 소수의 판별은 제곱근까지만 확인해도 충분하다. num의 제곱근보다 작은 수에서 안 나눠지면 제곱근 보다 큰 수에서도 안 나눠진다.

 

📝 에라토스네테스의 체

let solution = (n) => {
    let arr = Array(n + 1).fill(true).fill(false, 0, 2);

    for (let i = 2; i < Number(n ** 0.5) + 1; i++) {
        if (arr[i]) {
            for (let j = i * i; j <= n; j += i) {
                arr[j] = false;
            }
        }
    }

    return arr;
}

console.log(solution(10000));

여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘이다.

• 2부터 n까지의 모든 자연수를 나열한다.
• 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
• 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다.)
• 더 이상 반복할 수 없을 때까지 2, 3번의 과정을 반복

 

정리

• 에라토스테네스의 체 : 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법.
  • 1은 제거
  • 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
  • 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
  • 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
  • (반복)