[프로그래머스-JS] level.1 소수찾기 <에라토스테네스의 체>, <Array.from()>, <Array.prototype.fill()>

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

프로그래머스

 

이 문제는 처음에 아 쉽네 하고 바로 풀었지만 효율성에서 시간초과되어서 시간이 조금 걸렸다. 

결국 에라토스테네스의 체로 풀었다. 

 

나의 코드 

 

풀이1)

function solution(n) {
    let arr = Array.from({length:n+1}, (v)=> true).fill(false, 0, 2);
    for(i = 2; i*i <n; i++){
        if(arr[i]){
            for(k= i*i; k<= n; k +=i){
                arr[k] = false
            }
        }
    }
    return arr.filter(x=>x).length;
}

 

먼저 0과 1은 소수에서 제외하고 전부 true이다. 

 

첫 번째 for문의  범위는 i*i가 n을 넘기 전까지 for문이 작동한다. 

에라토스테네스 체는 소수의 배수를 전부 제거 하는 것이기에  i*i가 n을 넘으면 의미가 없다. 

 

그리고 if문으로 넘어가서 arr[i] = true이면  

그 배수를 전부 false로 바꾼다. 

 

최종적으로 true만 추출하는 filter를 하고 그 배열의 길이를 출력하게 하면 정답이다. 

Array.from()

 

 

Array.from() 메서드는 유사 배열 객체나 반복 가능한 객체를 얕게 복사해 새로운 Array 객체를 만듭니다. 

 

console.log(Array.from('foo'));
// expected output: Array ["f", "o", "o"]

console.log(Array.from([1, 2, 3], x => x + x));
// expected output: Array [2, 4, 6]

 

빈 배열도 만들 수 있다.

Array.from({ length: 1 });
// [undefined]

Array.from({ length: 2 });
// [undefined, undefined]

Array.from({ length: 10}, (value, index)=> index + 1);
// [1,2,3,4,5,6,7,8,9,10]

 

Array.prototype.fill()

 

fill() 메서드는 배열의 시작 인덱스부터 끝 인덱스의 이전까지 정적인 값 하나로 채웁니다.

( 조심하자 끝 인덱스 전까지이다. )

 

const array1 = [1, 2, 3, 4];

// fill with 0 from position 2 until position 4
console.log(array1.fill(0, 2, 4));
// expected output: [1, 2, 0, 0]

// fill with 5 from position 1
console.log(array1.fill(5, 1));
// expected output: [1, 5, 5, 5]

console.log(array1.fill(6));
// expected output: [6, 6, 6, 6]

 

풀이 2)

function solution(n) {
    
    const primeNum = (num) =>{
        for(i=2; i<= Math.sqrt(num); i++) if(num % i === 0) return false;
        return num;
    }
    let result = [];
    for(k=2; k<= n; k++) if(primeNum(k)) result.push(k);
    return result.length;
}

 

 

 

 

에라토스테네스 체를 사용하지 않으면 확실히 오래 걸린다. 

다른사람 풀이

function solution(n) {
    const s = new Set();
    for(let i=1; i<=n; i+=2){
        s.add(i);
    }
    s.delete(1);
    s.add(2);
    for(let j=3; j<Math.sqrt(n); j++){
        if(s.has(j)){
             for(let k=j*2; k<=n; k+=j){    
                s.delete(k);
             }
        }
    }
    return s.size;
}

 

set을 통해서 홀수만 포함시키고  1을 지우고 2를 넣었다.

 

그리고 두 번째 for문을 통해 3부터  n의 제곱근의 수 만을 가지고  배수를 다 제거 하는 것이다. 

 

짝수를 제거하고 2만 넣고 홀수만 에라토스테네스 체를 사용하는 거와  홀수도 다 포함 시키고 하는 것과 큰 차이가 없다.