[ JS 기초 ] 소수 확인, 소인수 분해

01 소수 확인

자바스크립트로 소수를 판별하는 여러 방법 중 다음 두 가지를 구현하면 아래와 같다.

• 정석대로 판별하기 : 2부터 n까지 for문을 돌면서 나누어떨어지는지 확인
• 코드 최적화 > n 제곱근까지만 확인

 

01-1 소수 확인하기

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

console.log("5가 소수? ",isPrime(5))	// true
console.log("2가 소수? ",isPrime(2))	// true
console.log("8이 소수? ",isPrime(8))	// false
console.log("7이 소수? ",isPrime(7))	// true
console.log("11이 소수? ",isPrime(11))	// true

 

01-2 n제곱근까지만 확인하기
위 방법은 2부터 n까지 모두 돌아보면서 확인하기때문에 시간복잡도는 O(n)이지만, 위 코드를 수학적 관점에서 바라보면 좀 더 개선할 부분을 찾을 수 있다.

아이디어 1

• 어떤 숫자 n은 1Xn, 2Xn보다 좀 작은 수, 3X더 작은수, ... , n의 제곱근Xn의 제곱근 으로 표현할 수 있다.
• 결국 1을 확인했다면 n을 확인한 셈이고, 2를 확인했다면 n/2를 확인한 셈이고, 3을 확인했다면 n/3을 확인한 셈이다. 핵심은 1부터 n제곱근까지만 확인해도 n이 소수인지 아닌지를 판별할 수 있다는 의미다.

아이디어 2

• 소수를 나열해보면 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,71,73,79,83,89,97 ... 이런식으로 이어진다
• 잘 보면 나름의 규칙이 있다 (2,3만 제외)
  • 5 = 6*1 -1, 7 = 6*1+1
  • 11 = 6*2 -1, 13 = 6*2+1
  • 17 = 6*3 -1, 19 = 6*3+1
  • 23 = 6*4 -1, 25 = 6*4+1(제외)

모든 6의 배수 ±1 이 소수인 것은 아니지만, 2와 3을 제외한 소수는 모두 6의 배수 ±1 로 표현할 수 있다

이 아이디어를 자바스크립트 코드로 구현해보면 아래와 같고, 시간복잡도는 O(sqrt(n))으로 줄일 수 있다.

function isPrime(n) {
    if (n <= 1) {
        return false
    }
    if (n <= 3) {
        return true
    }
    if (n%2==0 || n%3==0) {
        return false
    }
    for (var i=5;i*i<=n;i=i+6) {
        // 제곱근 까지만 확인하되 6의 배수 기준으로 확인할 것
        if (n%i==0 || n%(i+2)==0) {
            return false
        }
    }
    return true
}

 

 

02 소인수 분해

알고리즘 문제를 풀다보면 어떤 수를 2,3,5,7의 곱으로 표현하라는 문제나 소인수분해를 해보라는 경우가 있다. 소인수 분해는 결국 제시된 수가 어떤 소수들의 곱으로 표현될 수 있는지 표현하는 것이다. 구현해보면 코드는 다음과 같다.

function primeFactors(n){
    while (n%2 == 0) {
        console.log(2)
        n = n/2
    }
    // 이제 n은 홀수 -> 이미 2의 배수를 판별했기때문에 2씩 증가시킬 수 있음
    for (var i=3;i*i <= n;i=i+2) {
        while (n%i==0) {
            console.log(i)
            n = n/i
        }
    }
    if (n>2) {
        console.log(n)
    }
}