[프로그래머스] 소수 찾기 (Level1)

문제

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

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

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

나의 풀이

function solution(n) {
    // 배열 생성 (2이상이므로 1개 확보)
    let result = 1;

    // for문 (3~n까지 하나씩 대입)
    for (let i = 3; i <= n; i++) {

    // for문 (i 나누기 2~n-1 => 나머지 0이면 빠져나감)
        for (let j = 2; j < i; j++) {
            if(i % j == 0) break;
            // n-1까지 나눴는데 나머지가 있다면 배열에 추가
            else if(j == i-1) result ++;
        }
    }
    return result;

 

• 정확도 테스트 결과
  
   
  이럴수가
  테스트 10부터 시간 초과로 실패했다.
  단순한 for문 중첩이 아니라 다른 방법이 필요했다.
   

해답

 
해답은 에라토스테네스의 체에 있었다
 

출처: 나무위키 https://ko.wikipedia.org/wiki/에라토스테네스의_체

 

function solution(n) {
    // 1. n+1 길이/ true로 채운 배열 생성
    let arr = new Array(n+1).fill(true);

    // 2. let end = n의 제곱근
    let end = Math.sqrt(n);

    // 3. 최종으로 반환될 결과값 변수 생성
    let result = 0;

    // 4. 2 ~ √n 순환할 for문 생성
    for(let i = 2; i <= end; i++) {

        // 5. 만약 arr[i] == false면 -> 다음 수로 넘어감
        if(arr[i] === false) continue;

    // 6. for문(i^2부터 n까지 제곱수 false로 변경)
        for(let j = i*i; j <= n; j += i) {
            arr[j] = false;
        }
    }

    // 7. 인덱스2부터 요소가 true의 갯수 반환
    for(let i = 2; i <= n; ++i){
        if(arr[i] === true){
            result++;
        }
    }
    return result;


    // 7-2. filter 사용
    // return arr.filter(el => el === true).length -2;
}

 

1. n+1 길이/ true로 채운 배열 생성
    
   맨 처음에는 숫자로 채운 배열을 만들고, 소수가 아니라면 삭제해줄 생각이었다.
   그런데 이게 생각보다 복잡하고 시간이 걸렸다.
   소수냐, 아니냐만 가려내면 되므로 인덱스를 숫자라고 보고 소수 여부를 boolean으로 표시하는 방법이 베스트다.
   new Array() 생성자는 배열의 길이만큼 배열을 생성한다.
   new Array(3) => array[0], [1], [2] 가 된다.
   우리는 인덱스를 숫자로 활용할 것이므로 n+1 길이의 배열을 생성해야 인덱스가 n까지 생성된다.
    

2. let end = n의 제곱근
    
   에라토스테네스의 체에 따르면, √n의 배수까지만 지워도 충분하다.
    

3. for문(i^2부터 n까지 제곱수 false로 변경)
    
   여기서 let j = i*i인 이유는 이러하다.
   예를 들어 i가 5라면 시작값은 25(55)인데 그 이유는
   10(52), 15(53), 20(54) 같은 이전 숫자들은 2, 3, 4의 배수라서 이미 false처리됐기 때문이다.
    

4. 인덱스2부터 요소가 true의 갯수 반환
    
   갯수 변환은 두 가지 방법이 생각났는데 for문과 array.filter를 이용한 것이었다.
   그런데 for문의 실행시간이 더 빠르게 측정되었다.
    

   • 7-2 arr.filter(el => el === true).length -2 => arr.filter(el => el).length -2
     오른쪽과 같이 더 간단하게 고칠 수 있다. 요소값이 true인 값을 고르는 것이기 때문이다.
      
     정확도 테스트 결과
     
      
     7-2 정확도 테스트 결과
     
      
      

참고

나무위키: 에라토스테네스의 체

velog.io/@goblin820

themarketer.tistory.com/73