[Programmers] 소수 찾기, 에라토스테네스의 체

문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

코드

풀이

주어진 숫자가 배열 형태가 아니므로, 첫 번째로 반복문을 등장시켜서 소수를 찾기 위한 숫자 집합을 만들어준다. 1은 자연스럽게 제외가 되니 2부터 시작해 n까지 배열에 넣어준다.
이때 arr[0], arr[1]은 채워지지 않아서 undefined이 될 것이지만, 구하는 것은 소수의 개수이므로 filter 메서드를 통해서 지워나갈 수 있다.

만들어진 배열을 순회하면서 소수가 아닌 수들을 제거해줄 목적으로 0을 넣어준다. i = 2일 때, i번째에 위치한 배열의 원소가 0일 경우 continue로 다음 for문 코드 진행으로 넘어간다. 배열의 인덱스와 해당 원소의 값은 동일한 숫자이므로, i + i는 i의 배수, 소수가 아니므로 0으로 만들어주고, 다시 여기에 i를 더해 다음 번 원소 값을 탐색한다.

코드 개선

빈 배열을 만들고 여기에 하나씩 숫자를 넣어 배열을 채우는 방법도 있지만, 차례 차례 증가하는 숫자를 배열화하는 깔끔한 코드도 있다. ES6 문법에서 Array from()과 keys() 메소드를 쓸 수 있다.

Array.from(Array(10).keys())

// spread operator를 이용해 더 짧게 표현하면 아래와 같다. 

let s = [...Array(10).keys()] 
console.log(s)

/* expected : [
  0, 1, 2, 3, 4,
  5, 6, 7, 8, 9
] 
*/

위 코드는 항상 0부터 채워나가기 때문에 만일 1부터 시작하도록 한다면, 아래처럼 써볼 수 있을 것이다.

let s = [...Array(10).keys()].map(el => ++el);

// or

let s = Array.from(Array(10), (e, i) => ++i)
let s = Array.from({ length: n }, (e, i) => ++i) // 위와 동일하다.

Array.from(arrayLike[, mapFn[, thisArg]])

• arrayLike : 배열로 변환하고자 하는 유사 배열 객체나 반복 가능한 객체
• mapFn : 배열의 모든 요소에 대해 호출할 매핑 함수
• thisArg : mapFun 실행 시 this로 사용할 값

출처

MDN Array.from()
How to create an array containing 1 .. N