1. 문제 설명

• 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
• 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.(1은 소수가 아닙니다.)

2. 제한 조건

• n은 2이상 1000000이하의 자연수입니다.

3. 입출력 예

let output = solution(10);
console.log(output); // 4

let output = solution(5);
console.log(output); // 3

4. 입출력 예 설명

입출력 예 #1: 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2: 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

5. 문제 풀이

function solution(n) {
    const isPrime = (num) => {
        if (num % 2 === 0) return false;
        
        let sqrtNum = parseInt(Math.sqrt(num));
        for (let i = 3; i <= sqrtNum; i += 2) {
            if (num % i === 0) return false;
        }
        return true;
    }
    
    let count = 1;
    for (let i = 3; i <= n; ++i) {
        if (isPrime(i)) ++count;
    }
    return count;
}

6. 문제 풀이 해설

function solution(n) {
    // 분석
    // 소수를 구하는 방법을 이해해야 한다.
    // 소수는 자기 자신과 1로만 나누어 떨어진다. (단, 1은 소수가 아님)
    // 1은 입력 안되므로, 2부터 n직전까지 반복문을 돌리면서 체크줘야 한다.
    // 하지만 제곱근과 소수의 관계를 안다면 더 효율적으로 풀 수도 있다.
    // 루트 n을 씌워 소수점을 자른 값까지만 체크하면, 
		// n이 소수인지 아닌지를 파악할 수 있기 때문이다.
    
    // 풀이
    // 우선 소수 체킹 함수를 구현한다.
    const isPrime = (num) => {
        // 우선 2로 나누어 떨어지는지 체크
        if (num % 2 === 0) return false;
        // 제곱근에 내림한 값으로 변환시키고
        let sqrtNum = parseInt(Math.sqrt(num));
        // 3부터 변환한 값까지로 나누어 떨어지는지 체크
        for (let i = 3; i <= sqrtNum; i += 2) {
            if (num % i === 0) return false;
        }
        return true;
    }
    
    // 카운트를 선언하고 반복문을 돌린다.
    // count는 1로 준다. 2는 짝수 중 유일한 소수이기 때문에 카운트를 하고 시작한다.
    let count = 1;
    // 3부터 시작해서 n까지 돌린다. 소수인지 아닌지는 구현한 함수부로 체크한다.
    for (let i = 3; i <= n; ++i) {
        if (isPrime(i)) ++count;
    }
    return count;
}