[자바스크립트로 하는 자료 구조와 알고리즘] 2장 자바스크립트의 독특한 특징

숫자 알고리즘 - 소수 테스트

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; 6*i<=n; i=i+6){
        if(n%i==0||n%(i+2)==0)
        return false;
    }

    return true;
}

소인수 분해

function primeFactors(n){//10
    while (n%2 == 0) {
        console.log(2);
        n = n/2;//5
    }
    for(let i = 3; i*i <= n; i = i+2){
        while (n%i == 0) {
            console.log(i);
            n = n/i;
            //i로 나눌 수 있을 때까지 나누고 더이상 안나눠지면 while탈출
            //n이 더이상 나눌 수 없는 수가 되면 while문을 돌지못함
            if(n==1)break;
        }
        //for문 조건 i*i <= n에서 탈락할 때 까지 동작
    }
    if(n > 2)console.log(n);
    //for문 조건에서 탈락하면 console.log안되니까 한번 더 if문으로 출력
}

연습문제 2

n보다 작은 모든 소수를 출력

function allPrimeLessThanN(n) {
    for(let i = 0; i < n; i++){
        if(isPrime(i) == true)console.log(i);
    }
}

연습문제 3

소인수 집합 확인하기(관례상 1이 포함된다)

function maxDivide(number,divisor) {
    while(number % divisor == 0) {
        number /= divisor;
    }
    return number;
}

function isUgly(number) {
    number = maxDivide(number, 2);
    number = maxDivide(number, 3);
    number = maxDivide(number, 5);
    return number === 1;
}

function arrayUglyNumber(n) {
    let uglyNumbers = [];
    let currentNumber = 1;//0이면 maxDivide에서 무한루프 걸림
    while(uglyNumbers.length < n) {
      //책에선 counter을 썻지만 unglyNumbers.length로 조건을 걸어도 됨
        if(isUgly(currentNumber)){
            uglyNumbers.push(currentNumber);
        }
        currentNumber++;
    }
    return console.log(uglyNumbers);
}