LearnApplyShare

[알고리즘] 소수 찾기

May 02, 2018 - [prime]

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