프로그래머스: 소수 찾기(연습문제)

1. 문제

• 문제 이해하기는 쉽다. 범위 안에서 소수의 개수 찾기
• 하지만 풀긴 어려웠다. 나한텐 다 어렵다ㅠ

2. 해결 과정

• 처음은 단순히 이중 for문으로 돌렸다. 하지만 시간 초과로 실패하고 검색을 시작. 이중 for문을 쓸 순 있으나 더 효율적으로 작성해야 했던 것.
• 내 목표는 일단은 다양한 알고리즘을 접하고 다양한 해결 방법, 메서드 익히는 것이기 때문에 이전처럼 너무 시간을 끌지 않으려고 한다.
• 에라토스테네스의 체를 사용한다는 정보와 관련 코드를 발견했고, 코드를 살펴보았다.

  🚀에라토스테네스의 체

• 거의 ctrl+c ctrl+v처럼 보이지만 코드를 이해한 다음 내가 비슷한 방향으로 직접 작성해 본 것에 의의를 둔다.

3. 코드

• 순서 정리
  1. 0부터~입력받은 숫자(n)까지 배열에 담아준다.
  2. for문을 돌리면서 소수가 아니라면 해당 인덱스의 값을 0으로 바꿔준다.
  3. 숫자가 남아있는 배열의 길이를 반환한다.
  

function solution(n) {
    var answer = 0;
    var before = []
    for(var i=0; i<=n; i++){	//입력받은 숫자까지 배열에 담아줌
        before.push(i)
    }
    for(var j=2; j*j<=n; j++){
        if(before[j]){		//해당 배열의 값이 0이 아니라면
            for(var k=j*j; k<=n; k+=j){		//j*j값부터 j만큼 증가시키면서 k위치의 값을 0으로 만듦
                before[k]=0;
            }
        }
    }
    before[1] = 0;
    
    answer = before.filter((c)=>c).length
    
    return answer;
}

🔥for(var j=0; j*j<=n; i++){}와 for(var k=j*j; k<=n; k+=j){}는 이해하기 어렵기도 했고 나중에 다시 까먹을 것 같아서 나름대로 정리를 해봤다. 알고리즘의 진행을 이해못한 것이 아니고 왜 제곱을 사용했는지에 대한 정의? 증명?을 해서 분명히 알고 싶었다.
=>일단 이유와 원리는 알겠다. 하지만 말로 설명하기는 아직 무리인 것 같다.. 지금 이거만 붙잡고도 몇시간을 있었는데ㅠㅠ 하지만 내 목표는 내가 깔끔하게 이해하는 것+다음에 헷갈리거나 까먹을 때 봐도 바로 이해할 수 있도록 나만의 방법으로 정리하는 것 이었기 때문에 여기까지 정리하는 것으로 한다.

4. 후기

• 배고프다...