에라토스테네스의 체 소수 찾기 알고리즘을 자바스크립트로..?

😎시작하기전에 여담

오늘은 하루 종일 코플릿 문제를 푸는 시간이었읍니다.
전체적으로 쉽게 풀 수 있는 문제들로 구성되어 있어서
풀고나서 페어분과 다양한 자료구조,알고리즘에 대해 이야기 하는 시간을 가졌는데

잘 알고 있는 자료구조는 알기 쉽게 설명해줄 수 있지만
내가 잘 모르는 부분에 대해 이야기할 때는
설명이 장황해지고 나도 내가 뭔 소릴 하는건지 잘 모르겠는 상태에 놓임

그리고 말을 너무 많이 하다보니까
점점 목소리가 맛이 가기 시작함

아니 교수님들은 도대체 어떻게 하루 종일을 떠드는거죠?
반나절만 떠들어도 목이 못버티는데요..?

 

---

😎 에라토스테네스의 체

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

프로그래머스

코플릿 문제에서 가장 인상깊었던 부분은 소수찾기 알고리즘을 구현하는 부분이었습니다.
사실 예전에 프로그래머스 문제를 풀면서 최초의 벽을 느꼈던 시점이
소수 문제였기 때문입니다.

아직도 기억나는 저 위 링크의 문제....
소수찾기는 뭐 그냥 나머지 0인게 있으면 그건 소수가 아닌거잖아요
하면서 풀었는데

이제보니 제한조건이 n은 2이상 1000000이하의 자연수입니다.인것
당연히 평범한 이중 for문으로는 시간초과가 일어납니다.

1000000 ^ 2 100만의 2제곱은...  1,000,000,000,000 
즉 1조입니다.

아무리 현대 컴퓨터의 성능이 좋아졌다해도
근 1조번의 반복을 10초안에 하는건 무리

이중for문을 기반으로 제곱근, 짝수는 세지않기 등의 잔머리를 굴려봤지만
여지없이 시간초과가 일어나던 중
에라토스테네스의 체라는 소수찾기 방법론을 알게되었습니다. 

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

무려 나무위키에 개별 항목까지 개설 될 정도로 유명한 방법론인데
수학과 담쌓고 살던 전 저 문제를 풀면서 처음 알게되었어요

1조번의 반복... 하실래요?

---

😎어케 하는건데요

1. 일단 1부터 100까지 숫자를 쭉 쓴다.
2. 일단 소수도, 합성수도 아닌 유일한 자연수 1을 제거하자
3. 2를 제외한 2의 배수를 제거한다.
4. 3을 제외한 3의 배수를 제거한다.
5. 4의 배수는 지울 필요 없다.(2의 배수에서 이미 지워졌다.
그러면 2, 3 다음으로 남아있는 가장 작은 소수, 즉 5를 제외한 5의 배수를 제거해야 한다.
6. 그리고 마지막으로 7을 제외한 7의 배수까지 제거

나무위키에 따르면 위와 같은 방법을 통해 제거한다고 합니다.
직접 링크에 들어가서 예시를 보면 훨씬 이해가 잘되니까 직접 가보시는걸 추천드리고
저 텍스트와 gif 예시만으로도 이해가 되시면 그냥 그런거구나 하고 넘어가시면 되겠습니다.

---

😎아니 그래서 알겠으니까 어떻게 코드 쓰면 되는데요

function solution(num) {
    let arr = Array(num + 1).fill(true);
    arr[0] = false;
    arr[1] = false;

    for (let i = 2; i * i <= num; i++) {
        if (arr[i]) {
            for (let j = i * i; j <= num; j += i) {
                arr[j] = false;
            }
        }
    }

    return arr.filter((el) => el).length;
}

간단합니다.
배열을 생성하고 배열안을 true로 가득 채워줍니다.
배열의 인덱스와 숫자는 1:1 매칭이 됩니다.
arr[0] 은 0을 뜻한다는 뜻입니다.

아래에 주석으로 설명을 한 코드를 작성했으니 참고해보세요

function solution(num) {
    let arr = Array(num + 1).fill(true);
    //숫자로 입력받은 num 매개변수보다 공간이 1 더 많은 배열을 생성해줍니다
    //배열은 0부터 시작할것이기때문에 +1을 하지 않으면 num에 비해 공간이 1부족해져요
    //모든 배열의 요소를 true로 채워줍니다.(fill은 특정 값으로 배열의 요소들을 채워주는 메서드입니다.)
    
    arr[0] = false;
    //0은 소수가 아니니 false를 할당합니다.
    
    arr[1] = false;
	//1역시 소수가 아니니 false를 할당합니다.
    //배열은 문자열과 달리 특정 인덱스의 값을 변경하는 것이 가능합니다.
    //왜 문자열은 안되고 배열은 되냐? 이건 뒤에 서술하겠습니다.
    
    for (let i = 2; i * i <= num; i++) {
    // 에라토스테네스의 체는 2,3,5,7의 배수를 제거합니다
    // 4는 앞서봤듯이 2에서 이미 다 제거되지만 굳이 예외처리하는것보다
    // 그냥 i++을 통해 값 한개씩 올려나가도 무방하기때문에 i++을 사용합니다.
    
        if (arr[i]) {
        // 만약 arr의 해당 인덱스가 true라면(즉 false가 할당되지않았다면)
            for (let j = i * i; j <= num; j += i) {
                arr[j] = false;
            }
            //반복문을 통해 false를 할당해줍니다.
        }
    }

    return arr.filter((el) => el).length;
    // 해당 코드는 특정 숫자까지 몇개의 소수가 있는지를 찾는 코드였으므로
    // 배열메서드 filter를 이용해 요소의 값이 true인 케이스만 뽑아서 길이를 재준것입니다.
}

num에 100을 인자로 전달한 결과

우리가 원하는대로 잘 구현이 되었을까요?

앞서 배열의 인덱스와 수는 1:1대응이라고 생각한다 했습니다.

0은 소수가 아니니 false

1은 소수가 아니니 false

2는 소수이니 true

3도 소수이니 true

4는 소수가 아니니 false

5는 소수이니 true

 

앞줄만 봤는데 대충 맞는것같군요

요소의 값이 true인 것은 소수이고 아닌 것은 false입니다.

이 에라토스테네스의 체는 시간복잡도 면에서 굉장히 유리하게 응용할 수 있지만

너무 많은 공간을 필요로 할 수도 있습니다. (만들어야할 배열의 크기가 1조개라면 어떨까요?) 

관련된 정보가 인터넷에도 많으니 더욱 관심이 생기신다면

좀 더 찾아보시는 것도 좋을 듯 합니다.

---

😎그래서 문자열은 index로 변경이 안되는 이유가 뭔데?

그것은 자바스크립트의 프로퍼티 어트리뷰트와 밀접한 관련이 있습니다.

자바스크립트의 프로퍼티 어트리뷰트 내부 슬롯은

다음과 같이

Object.getOwnPropertyDescriptors()

메서드를 이용해 확인을 할 수 있습니다.

이 슬롯에는 각각 value , writable, enumerable, configurable 들이 존재하는데

writable 속성을 주목해서 보시면

writable이 true인 배열은 값을 변경할 수 있고(쓰기)

writable이 false인 문자열은 값을 변경할 수 없습니다.

 

configurable이라고 생각하고 있었는데 잘못된 정보를 적어서 급히 수정합니다.

크로스 체킹이 중요하네요..

https://ko.javascript.info/property-descriptors

모던자바스크립트 튜토리얼의 설명은 다음과 같습니다

writable이 true이면 값을 수정할 수 있고 그렇지 않다면 읽기만 가능하다고 하네요!

 

이로인해 writable이 false인 문자열은 값을 수정할 수 없고

writable이 true인 배열은 값을 수정할 수 있는 것입니다.