[프로그래머스] 소수 찾기 - 자바스크립트

 

직접 짠 코드가 몇 개 시간초과가 떠서, 결국 에라토스테네스의 체를 검색하여 풀었다. 

 

 

문제 설명

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

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

제한 조건

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

입출력 예nresult

10	4
5	3

입출력 예 설명

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

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

 

 

문제 풀이

function solution(n) {
    var answer = 0;
    const arr = [];
    
    for (let k = 0; k < n+1; k++) {
        arr.push(true);
    }
    
    for (let i = 2; i * i <= n; i++) {
        if (arr[i]) {
            for (let j = i*i; j <= n; j+= i) {
                arr[j] = false;
            }
        }
    };
    
    arr.splice(0,2, false, false);
    
    const result = arr.filter((v) => {return v !== false});
    
    answer = result.length;
        
    return answer;
}

 

 

에라토스테네스의 체

에라토스테네스가 발견한 소수를 찾는 방법.

 

개념

- 모든 자연수는 소수들의 곱으로 표현된다.

- 그래서 주어진 숫자 값의 범위 안에서, 자신을 제외한 배수 값을 지워나간다.

- 그럼 결국 소수만 남게 된다.

 

 

구현

2부터 N까지 자신을 제외하고 순차적으로 자신의 배수들을 지워가면 결국 소수들만 남는다.

 

n까지가 아니라 √n까지만 검사해도 결과는 같은데, 그 이유는 아래와 같다.

 

 

어떤 수 n 을 a*b로 표현할 수 있다.

 

a와 b의 관계식은 a <= b 이다.
(만약 a > b 이면 두 수를 바꿔서 b <= a 라고 표현할 수 있다.)

 

a와 b의 차이가 최소로 날 때 그 값은 √n*√n = n 이 나온다.
따라서 n이 axb로 표현될 수 있고, a <= b일 때, b의 최소값이며 a의 최대값은 √n이다.

• a가 √n보다 크게 되면, a*b > n
• b가 √n보다 작게 되면, a*b < n
• 따라서 a <= b일 때, a <= √n, b >=√n이다.
  a와 b의 차이가 가장 작은 경우는 a와 b가 서로 √n이 되는 경우이다. 그러므로 √n까지만 반복해보면 이 수가 소수인지 알 수 있다.

예시)
n = 18 이라고 가정해보자.
18의 약수는 1, 2, 3, 6, 9, 18 이다.
이는 1x18, 2x9, 3x6 의 결과이다.
이들은 반비례 관계로 몫이 커지면 나누는 값이 작아지거나, 나누는 값이 커지면 몫이 작아진다. n의 제곱근까지 계산하게 되면 이후 몫과 나누는 값은 반대로 바뀐다.

• 따라서 n의 제곱근까지, 그러니까 a와 b가 서로 √n이 될 때 까지만 반복해보면 이 수가 소수인지 알 수 있다.

 

 

 

참고

소수(Prime number) 판별법 [ JavaScript ]