[TIL] 230330 에라토스테네스의 체
https://school.programmers.co.kr/learn/courses/30/lessons/12921
에라토스테네스의 체
에라토스테네스의 체는 '특정 범위 내의 소수'를 판정하는 데에만 효율적이다. 만약 주어진 수 하나가 소수인가? 만을 따지는 상황이라면 이는 소수판정법이라 해서 에라토스테네스의 체 따위와는 비교도 안되게 빠른방법이 넘쳐난다.
한편, 에라토스테네스의 체를 이용해 1~n까지의 소수를 알고 싶다면, n까지 모든 수의 배수를 다 나눠 볼 필요는 없다. 만약 n보다 작은 어떤 수 m이 라면 와 중 적어도 하나는 루트 이하이다. 즉 n보다 작은 합성수 m은 루트 보다 작은 수의 배수만 체크해도 전부 지워진다는 의미이므로, 루트 이하의 수의 배수만 지우면 된다.
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://mine-it-record.tistory.com/507
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/Array
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/fill
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/filter