[TIL] 230330 에라토스테네스의 체

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

프로그래머스

에라토스테네스의 체

에라토스테네스의 체는 '특정 범위 내의 소수'를 판정하는 데에만 효율적이다. 만약 주어진 수 하나가 소수인가? 만을 따지는 상황이라면 이는 소수판정법이라 해서 에라토스테네스의 체 따위와는 비교도 안되게 빠른방법이 넘쳐난다.

한편, 에라토스테네스의 체를 이용해 1~n까지의 소수를 알고 싶다면, n까지 모든 수의 배수를 다 나눠 볼 필요는 없다. 만약 n보다 작은 어떤 수 m이 m=ab라면 a와 b 중 적어도 하나는 루트n​이하이다. 즉 n보다 작은 합성수 m은 루트n​보다 작은 수의 배수만 체크해도 전부 지워진다는 의미이므로, 루트n​ 이하의 수의 배수만 지우면 된다.

 

ex) n = 49, m = 48이고 a가 6, b가  8이라면 -> 적어도 하나의 수 a는 루트 n인 7보다 작다.

 

function solution(n) {
  let arr = Array(n + 1)
    .fill(true)
    .fill(false, 0, 2);

  for (let i = 2; i * i <= n; i++) {
    if (arr[i]) {
      for (let j = i * i; j <= n; j += i) {
        arr[j] = false;
      }
    }
  }

  return arr.filter((e) => e).length;
}

console.log(solution(10));

 

1. Array(n+1) 로 length가 n+1인 빈 슬롯을 가진 배열을 만든다.

function solution(n) {
  let arr = Array(n + 1);
  return arr;
}

console.log(solution(10)); // [ <11 empty items> ]

왜 n+1 일까?

배열의 index가 0부터 시작하기 때문.

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이어야 arr[0] = 0 이렇게 0부터 자연수 n까지 요소들을 순서대로 넣을 수 있다.

단일 매개변수 배열 생성자

배열을 생성자와 하나의 숫자 매개변수로 생성할 수 있습니다. 그 결과는 length가 매개변수고, 길이만큼의 빈 슬롯을 가진 배열입니다.

let fruits = new Array(2)

console.log(fruits.length) // 2
console.log(fruits[0])     // undefined

 

2. fill(true)로 모든 요소를 true로 만든 다음, fill(false, 0, 2)로 0과 1에 해당하는 값을 false로 바꾼다. 0과 1은 소수가 아니기 때문.

function solution(n) {
  let arr = Array(n + 1)
    .fill(true)
    .fill(false, 0, 2);
  return arr;
}

console.log(solution(10));
/* [
  false, false, true,
  true,  true,  true,
  true,  true,  true,
  true,  true
] */

 

3. 에라토스테네스의 체로 2부터 자연수 n까지의 소수 판별하기

3-1. let i=2 2부터 반복문을 돌림. i*i <=n i 의 제곱이 n보다 작거나 같은 동안 반복할 것임. i++ i는 계속 증가

ex) n이 10일 때 console.log(i)하면 2 3이 나옴

3-2. arr[i] 는 true 임. if문으로 true인 경우 이중 반복문을 돌리도록 함

3-3. 이중 반복문으로 배수를 모두 false로 바꿈.

ex) n이 10일 때 console.log(j)하면 4 6 8 10 9가 나옴

i = 2 일 때 j = 4이고 j+=i 로 j 는 4 6 8 10 이렇게 증가함

3-4. 배열 arr 을 filter((e) => e) 로 true만 있는 새로운 배열로 반환하고 그 length를 구함.

-> i = 루트 j (i * i 즉 i 의 제곱은 j)

-> true는 소수 false는 소수가 아닌 수

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

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

https://velog.io/@jakeseo_me/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-14-%EC%86%8C%EC%88%98-%EC%B0%BE%EA%B8%B0-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

코딩테스트 #14 소수 찾기 (에라토스테네스의 체)

https://mine-it-record.tistory.com/507

[알고리즘] 소수 찾기 - 에라토스테네스의 체 by javascript

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/Array

Array() 생성자 - JavaScript | MDN

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/fill

Array.prototype.fill() - JavaScript | MDN

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/filter

Array.prototype.filter() - JavaScript | MDN