소수구하기

해당 내용은 프로그래머스 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 공부하며 정리한 내용입니다.

방법 1. 1~부터 일일히 나누기
시간 복잡도 : O(n)
가장 비효율적인 방법, 코테에서 쓰지 않을것

방법 2. 소수는 N의 제곱근보다 큰 수로 나눠지지 않는 다는 점 이용

방법 1의 경우처럼 1부터 끝까지 나누면 중간부터는 겹치기 마련임. 예를들어, 1 곱하기 100 (= 100 곱하기 1)
그러므로 제곱만 체크해도 소수를 판단할 수 있음

이를 통해 개선된 효율성은 시간 복잡도 : O(root(n))

방법 3. 에라토스테네스의 체

예전에 공부 했던 적이 있는데 2의 배수들을 지우고 3의 배수들을 지우고 차례대로 해나가며 방법 2번(제곱근까지)을 적용 범위로 처리해 진행.

고로 지워지지 않은 숫자들은 전부 소수가 됨.

방법 2는 숫자 하나의 소수 여부를 판단하는데 쓰는 알고리즘이지만 방법 3은 특정 범위 안에 소수들을 찾아내는 방법.

시간복잡도 O(n log(logn))