소수찾기

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

n을 2부터 n-1까지 수로 나눠 나머지가 0인지 확인하면됩니다
위의 시간복잡도는 O(n)이다.하지만 더효율적인 방법으로 계산하자면

우선 소수를 나열하자면 2,3,5,,7,11 .....
2와3을 제외하고는 6x+-1 의 형태를 지닌다.

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

    return true;
}

위의 코드의 시간복잡도는 o(sqrt(n))이다.

소인수분해

function primeFactors(n){ //2로나눌수있을떄가지 나누기
    while (n%2 == 0) {
        console.log(2)
        n = n/2
    }
  
   
    for (var i=3;i*i <= n;i=i+2) { //n은 홀수이기떄문에 2씩증가
        while (n%i==0) {
            console.log(i)
            n = n/i
        }
    }
  //n이 2보다큰 소수인 경우를 위해 처리
    if (n>2) {
        console.log(n)
    }
}