프로그래머스 1단계 - 소수 찾기

1 단계 : 소수 찾기

코딩테스트 연습 > 연습문제 > 소수 찾기

---

문제 설명

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) {
    const primes = []; // 소수 찾기 배열
    
    // 0~n까지의 소수 판별여부를 담은 (true, false) 배열
    const toArr = Array.from(Array(n+1).keys(), x => {
        if(x === 0 || x === 1) return false;
        else return true;
    });
    
    /** 
    이부분은 판별여부를 담은 toArr에서 하나씩 꺼내와서 true이면 primes에 넣는다
    다만 소수가 아닌 수를 거르기 위해서는 2부터 들어오는데 2의 배수를 다 거릅니다 (false로 만들어서)
    3이 들어오면 3의 배수 거릅니다.
    4가 들어오면 4의 배수 거릅니다... 이렇게 쭉 다 걸러서 n까지 도달하면 소수만 배열에 담기게 됩니다.
    에라토스테네스의 체라고 했던가요?
    */
    for(let i = 0; i < toArr.length; i++){
        if(toArr[i]) primes.push(i);
        
        if(i === 0 || i === 1) continue;
        for(let j = i * 2; j <= n; j+=i){
            toArr[j] = false;
        }
    }
    return primes.length;
}

리뷰

순서는 다음과 같다
1. 에라토스테네스의 체를 설명드릴게요 n까지의 소수 판별여부를 담은 배열 toArr선언 합니다. (0~n)까지 입니다. 0,1은 false (소수가 아니죠)
2. 로직은 들어보면 간단합니다. 2의배수 제외하고 3의배수 제외하고 4의 배수 제외하고 하면 배수가 아닌 수들만 남겠죠?
3. toArr을 순회하면서 true(소수인것들)만 primes 배열에 추가합니다.
4. 밑에서는 i의 배수를 지우는 과정입니다.

총평 : 반복문을 돌아서 소수를 찾을 수 있겠으나, 효율성에서 안되서 눈물을 머금고 이방법을 썼습니다.

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