[에라토스테네스의 체] 프로그래머스 소수 찾기 - JS

✏️ 문제 설명

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를 반환

 

---

✏️ 문제 풀이

function solution(n) {
    let result = new Array(n);
    // 2 ~ n 범위
    for (let i = 2; i <= n; i++) {
        // 자기 자신의 인덱스로 그 값을 초기화해준다
        result[i] = i;
    }

    for (let i = 2; i <= n; i++) {
        // 이미 지워진 숫자라면 무시
        if(result[i] == 0) continue;
        
        // 이미 지워진 숫자가 아니라면 그 배수(i의 배수)부터 시작해서 가능한 모든 숫자를 지워준다
        for (let j = i+i; j <= n; j += i) {
            // 0이라는 의미 = 지워진 숫자
            result[j] = 0;
        }
    } 
    return result.filter(x => x !== 0).length
}

안 풀려서 에라토스테네스의 체로 구현한 c언어 풀이를 보고 풀었다.

주석을 읽어도 이해가 잘 안된다면 하단에 첨부한 링크 동영상을 보자.

 

에라토스테네스의 체란?

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

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

=> 소수를 구하고자 하는 구간의 모든 수(1은 x, 2부터~)를 나열한 후 2, 3, 5, 7을 제외하고 이 숫자들의 배수를 모두 지워주면 된다.

 

 

▶ Array() constructor

new Array(element0, element1, /* … ,*/ elementN)
new Array(arrayLength)

Array(element0, element1, /* … ,*/ elementN)
Array(arrayLength)

Array 객체 생성자. 

 

 

참고 사이트

 

air.luca.log

- 이분의 블로그에서 동빈나 유튜브 예전 알고리즘 강의를 발견했는데 천천히 말해주시고 이해가 잘 되는 넘 좋은 강의다. 감사합니다.

24강 - 에라토스테네스의 체 [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #24 ]

처음 음악이 넘 웅장해서 놀랐는데 그럴만한 위엄이 있다..

 

 

🙂 공부하며 정리하는 글입니다. 공감과 피드백 환영합니다.