JS 숫자 알고리즘

숫자가 소수인지 판단하는 알고리즘은 수자와 관련된 가장 많이 논의된 알고리즘 중 하나라고 한다.
이를 한번 살펴보자.

소수 테스트

숫자가 소수인지 알아보는 방법은 숫자 n을 2부터 n-1까지의 수로 나눠 나머지가 0인지 확인하면 된다.

const isPrime=(n)=>{
    if(n<=1){
        return false
    }

    // 2부터 n-1까지의 수로 나눈다.
    for(let i =2 ; i<n;i++){
        if(n%i===0){
            return false
        }
    }

    return true
}

위의 코드의 시간 복잡도는 O(n)이다. 0부터 n까지의 모든 수를 확인하기 때문이다.

위의 알고리즘 수행 방식에서 패턴을 찾아 알고리즘을 더 빠르게 만들 수 있을까?

우선 2의 배수는 무시해도 된다. 하지만 이뿐만 아니라 최적화 가능한 부분이 더 있다.

우선 소수를 나열해보면

2,3,5,7,11,13,17,19,23,29 ...

알아차리기 힘들 수도 있지만 2와 3을 제외하고는 모든 소수는 6k +- 1의 형태를 지닌다.
여기서 k는 정수다.

5 =(6-1), 7 = (6+1) , 11 = (2*6 -1) ...

또한 n이 소수인지 알아보기 위해 반복문을 n의 제곱근까지만 확인해보면 된다. n의 제곱근이 소수가 아니면 n은 수학 정의에 의해 소수가 아니기 때문이다.

const isPrime = (n)=>{
    if(n <= 1 ) return false
    if(n <=3 ) return true

    //입력된 수가 2 또는 3인 경우 아래 반복문에서 
    //다섯 개의 숫자를 건너뛸 수 있다.

    if(n%2 ===0 || n%3===0) return false

    for(let i =5;i*i<=n; i +=6){ 
        //i*i <=n 인 이유는 제곱근이기 때문
        if(n%i===0 || n%(i+2)===0){
            return false
        }

    }

    return true;
}

위의 개선된 알고리즘의 시간복잡도는 O(sqrt(n)) 이다. 시간을 상당히 줄인다.

소인수분해

또 다른 유용하 알고리즘으로 어떤 숫자의 소인수분해를 구하는 것이 있다. 소수는 암호화와 해싱의 기반이 되고 소인수분해는 주어진 숫자를 만들기 위해 어떤 소수들이 곱해져야 하는지 구하는 과정이다.

const primeFactors=(n)=>{
    // n이 2로 나눠진다면 나눠질 수 있는 수만큼 2가 출력된다.
    while(n%2 ==0){
        console.log(2)
        n /= 2
    }

    //이 지점에서 부터 n은 홀수이다.
    //따라서 수를 두 개씩 증가시킬 수 있다.
    //3부터 n의 제곱근까지 반복한다.
    for(let i =3; i*i <=n ; i = i+2){
        while(n%i ==0){
            console.log(i)
            n /=i
        }
    }
	
    //n이 2보다 큰 소수인 경우를 처리하기 위한 조건문이다.
    if(n>2){
        console.log(n)
    }
}

primeFactors(10) -> '2'와 '5'를 출력한다.

무작위 수 생성기

무작위 수 생성은 어떤 조건이 어떤 식으로 동작하는지 확인하는 데 있어 중요하다.
JS에는 수자를 생성하기 위한 내장 함수인 Math.random()이 있다.

Math.random()은 0과 1 사이의 부동소수점을 반환한다.

무작위 정수나 1보다 큰 무작위 수를 얻는 방법은
Math.random()에 범위를 곱하면 된다.

Math.random()*100  // 0부터 100까지의 부동소수점
Math.random()* 25+5 // 5부터 30까지의 부동소수점
Math.random()*10-100 // -100부터 -90까지의 부동소수점

무작위 정수를 얻기 위해서는 Math.floor(), Math.round(),Math.ceil()을 사용해 부동소수점을 정수로 만들면 된다.

Math.floor(Math.random()*100)  // 0부터 99까지의 정수
Math.round(Math.random()* 25+5) // 5부터 30까지의 정수
Math.ceil(Math.random()*10-100) // -100부터 -90까지의 정수