[알고리즘] 소수 찾기

Problem

• 1부터 n까지 모든 소수를 찾는 알고리즘

Concept

1. 2부터 n까지 자연수를 요소로 갖는 배열 arr 생성 [2, 3, 4, ..., n]
2. 빈 배열 primes 를 생성
3. arr 배열의 첫번째 요소(arr[0])를 primes 배열에 추가
4. arr 배열에서 arr[0] 의 배수를 모두 제거
5. 위 3~4과정을 arr[0] 이 n/2 보다 커지기 전까지 반복
6. 위 과정이 끝나고 primes 배열과 arr 배열을 합치면, 1부터 n까지의 모든 소수를 얻게됨

JS Code

Ref.

https://programmers.co.kr/learn/challenge_codes/21