반응형
에라토스테네스의 체
-
소수의 개수 파악 - 에라토스테네스의 체Algorithm/이론 2023. 1. 1. 19:27
에라토스테네스의 체는 특정 수가 주어졌을 때 2부터 특정 수까지의 범위 중 소수의 개수를 파악하는 방법이다. 알고리즘의 순서는 아래와 같다. 2 부터 구하고자 하는 구간의 모든 수를 나열한다. 첫번째 수인 2 자기 자신을 제외하고 자신의 배수를 모두 지운다. 남은 수들 중 다음수에 대하여 단계 2를 반복한다. 이를 자바스크립트 코드로 구현하면 아래와 같다. function solution(n) { // 1. 2부터 n까지의 모든수를 배열에 저장 let arr = new Array(n - 1).fill(2).map((ele, idx) => ele += idx); for (let i = 0; i < arr.length; i++) { // 2. 모든 수에 대해 순회 // 3. 인덱스의 수가 0일 경우(지워진 ..