프로그래머스 코딩테스트 [소수찾기] - Javascript

소수 찾기

 

문제 설명

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

 

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.

(1은 소수가 아닙니다.)

 

제한 조건

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

 

입출력 예

n result

10 4

5 3

 

입출력 예 설명

입출력 예 #1

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

 

입출력 예 #2

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

 

 

// 첫 번째 답안. 하지만, 효율성 테스트에서 Fail
function solution(n) {
    let answer = 0;

    let startTime = new Date();
    
    for (let i = 2; i <= n; i++) {
        isPrime(i) ? answer++ : null;
    }
    
    let endTime = new Date();
    let gapTime = endTime.getTime() - startTime.getTime();
    console.log('gapTime: ', gapTime + "ms");

    return answer;
}

function isPrime(n) {
    if (n === 1)
        return false;

    if (n === 2) {
        return true;
    }

    /**
     * 2부터 주어진 자연수 n까지 모든 수를 하나씩 나누어도 같은 결과가 나오지만
     * 자연수 n의 약수 쌍의 경우, 반드시 둘 중 하나는 n 제곱근 이하이기 때문에 
     * 제곱근까지만 나누어 확인할 경우 속도를 개선할 수 있다.
     */
    let size = Math.ceil(Math.sqrt(n));
    for (let i = 2; i <= size; i++) {
        if (n % i === 0)    
            return false;
    }

    return true;
}

// 두 번째 답안
/**
 * 에라토스트테네스의 체를 활용하였다.
 *
 * 배열에 2부터 N까지의 모든 수를 담은 후
 * 소수가 아닌 것들을 모두 체크하는(ex. 0으로) 방식이다.
 * 
 * 1. 2부터 순차적으로 1씩 증가시키면서 N까지 증가한다.
 * 2. 2를 제외한 모든 2의 배수에는 0으로 체크,
 * 3. 3, 4도 마찬가지 ... 반복
 * 4. 결과적으로 0이 아닌 것들만 소수가 되는 방식
 * 
 * 참조
 * https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4
 */
function solution2(n) {
    let answer = 0;
    let arr = [];

    let startTime = new Date();

    // 빈 배열에 값 초기화
    for (let i = 2; i <= n; i++) {
        arr[i] = i;
    }

    for (let i = 2; i <= n; i++) {
        if (arr[i] === 0) // 이미 체크된 수의 배수는 확인하지 않는다
            continue;

        for (let j = i + i; j <= n; j += i) { // i를 제외한 i의 배수들은 0으로 체크
            arr[j] = 0;
        }
    }    

    // 0이 아닌 수들은 모두 소수이므로, answer을 증가한다.
    for (let i = 2; i <= n; i++) {
        if (arr[i] !== 0)
            answer++;
    }

    let endTime = new Date();
    let gapTime = endTime.getTime() - startTime.getTime();
    console.log('gapTime: ', gapTime + "ms");    

    return answer;
}
console.log(solution2(10));    // 4
console.log(solution2(100));   // 25
console.log(solution2(1000));  // 168 
console.log(solution2(50000)); // 5133

 

참조

https://programmers.co.kr/learn/courses/30/lessons/12921

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4