소수 찾기

소수 찾기

// https://programmers.co.kr/learn/courses/30/lessons/12921
function solution(n) {
  var answer = 0;
  let sosu = [];
  let arr = {};
  for (let i = 2; i <= n; i++) {
    arr[i] = 1;
  }

  for (let index = 2; index <= n; index++) {
    const element = arr[index];
    if (element == 0) {
      console.log('index', index);
      continue;
    }
    sosu.push(index);
    let a = 2;
    // 지금 현재 값을
    while (true) {
      if (!(arr[index * a] + 1)) {
        break;
      }
      arr[index * a++] = 0;
      console.log(index * a);
    }
  }
  console.log('소수:', sosu);
  return sosu.length;
}
result = solution(10);

• 효율성 통과하기 어려웠다

해설

• 정수 n을 입력받으면 1부터 n 사이의 소수의 개수를 반환한다
• 효율성을 통과할려면 에라토스테네스의 체를 써야한다

• 에라토스테네스의 체 알고리즘을 구현한다
• 글로 적힌거 봣는데 하나도 이해가 안되서, 위 그림을 보고 구현했다. (역시 그림이 최고!)
• 첫번째 반복문에서 2부터 n까지 1로 초기화한다
• 이제 2부터 n까지 반복문을 돈다
• 처음에 2는 소수다. 소수 배열에 추가하고 while루프에서 arr배열에서 2의 2배수를 전부 지운다
• 여기서 지운다는 것은 arr[2의배수] = 0 으로 만드는 것!
• 그러면 다음 루프 3… 똑같이한다
• 그다음 4에서 arr[4] == 0 이기때문에 바로 패스한다
• … 반복
• 내 글로된 설명보다 그림보는게 훨씬 이해에 빠를것이다!

에라토스테네스의 체

• 소수를 찾는 방법