[JS 알고리즘_17] 소수 찾기

Q) 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)

풀이

function checkPrime(num) {
    if(num === 2) return true;
    if(num % 2 === 0) return false;
    for(let i = 3; i*i <= num; i +=2){
        if (num % i === 0) return false
    }
    return true
}

function solution(n) {
    let answer = 0;
    for(let i=2; i<=n; i++){
        if(checkPrime(i)) answer ++
    }
    return answer;
}

1. 반복문을 돌려 n사이에 있는 소수의 개수를 반환한다.
2. checkPrime함수를 통해 소수인지 판별한다.

checkPrime함수

• 일단 2는 소수가 맞기 때문에 checkPrime에서 2가 매개변수로 들어왔을 시 true를 반환한다.
• 2를 제외한 짝수는 소수가 아니기 때문에 짝수이면 false로 나타낸다.
• 그외의 숫자는 for문을 돌려 홀수인 경우 소수인지 아닌지 판별한다.

(어렵다,,, !!!)
만약에 num이 9가 됐을 때 num % i인 즉 9 % 3 은 0이 되기 때문에 (9의 약수는 1,3,9이기 때문에) return false