[프로그래머스-JS] level.1 소수 만들기 <소수>

 

그새 또 소수 구하는 것을 까먹었다 다시 공부 ㄲ

 

 

서로다른 3개를 뽑을때는 for 3중첩 해주기

 

 

나의 코드

 

function solution(nums) {

    //서로다른 3개를 어떻게 뽑지?
    const isPrime = (num) => {
        if(!num || num === 1) return false;
        for(let i = 2; i < num; i++){
            if(num % i === 0) return false
        }

        return true
    }

    let box = 0;
    let result = [];
    for(i=0; i<nums.length; i++){ 
        for(k=i+1; k<nums.length; k++){
            for(j=k+1; j<nums.length; j++){
               box = nums[i] + nums[k] + nums[j]
                if(isPrime(box)){
                    result.push("true")
                }

            }

        }

    }
    return result.length;
}

 

 

소수구하는 여러가지 방법

 

소수란 1과 자기 자신으로 밖에 나누어떨어지지 않는 1 이외의 정수이다.

 

1. 단순 for 문 사용

const isPrime = (num) => {
    if(!num || num === 1) return false;
    for (let i = 2; i < num; i++) {
        if (num % i === 0) return false;
    }

    return true;
}

 

2. 제곱근 ( Math.sqrt) 사용

const isPrime = (num) => {
    if(!num || num === 1) return false;
    for (let i = 2; i  <= Math.sqrt(num) ; i++) {
        if (num % i === 0) return false;
    }

    return true;
}

 

 

예를 들면

25의 제곱근은 5이다. 

이때 5까지만 반복문이 돌아가더라도 25는 5의 배수이기에 i가 5일 때 나누어 떨어지게 되고 소수가 아님을 판별할 수 있게 된다.

 

하나 더 보자면

49의 제곱근은 7이다. 

49도 7의 배수이므로 i가 7일 때 나누어 떨어지므로 소수가 아님을 알 수 있다.

 

즉 만약 어떤 수 N의 제곱근보다 작은 수에서 약슈가 존재하지 않는다면, N의 제곱근보다 큰 수에서도 약수가 존재하지 않는다.

 

쉽게말해 

어떤 수 N의 약수는 항상 쌍으로 존재한다. 

곱해서 N이 되는 짝궁이 있다는 뜻이다.

즉 제곱근을 기준으로 그 곱은 대칭적으로 곱이 일어난다. 

 

예를 들어 16의 약수는 1, 2, 4, 8 16 있다.

16의 제곱근은  4이다. 

이때 16을 4(제곱근)까지만 나눠서 떨어지면 소수가 아니고

만약 제곱근까지도 나누어 떨어지지 않는다면 소수인 것이다.  

 

 

 

num의 제곱근보다 작은 수에서 나눠지는 수가 없다면

큰 수에서도 나눠지는 수가 나올 수 없기에 가능하다