[BOJ]1456:거의 소수(에라토스테네스의 체)

* 바킹독님 블로그를 참고하여 공부했다

 

[에락토스테네스의 체]

구현방식: N크기의 배열을 만들어 각 수의 배수를 소수가 아님(false)을 저장

i가 N에 도달할때까지 j가 2*i부터 시작하여 N까지 탐색

 

[에락토스테네스의 체 최적화]

에락토스테네스를 구현할 시 최적화는 필수이다.

최적화를 하지 않는다면 그냥 각각에 대해 소수를 판별하는 방법을 사용하는 것이 낫다.

최적화:

1) j = 2i가 아닌 i*i부터 시작

2) i*i <= N 인 경우에만 반복문

3) 소수 판정값은 0, 1이 아닌 Boolean 타입인 True, False로 하여 메모리 절약(cache hit rate도 증가됨)

시간복잡도: O(NlgNlogN)

 

(개념 복습 차원에서 푼 BOJ 소수구하기: github.com/SuyeonChoi/Algorithms/blob/master/BaekJoon/Python/%EC%88%98%ED%95%99/p1929.py )

 

개념을 완벽하게 이해하니 문제는 풀만했다. 하지만 범위 설정 조건이 달라지면 많이 헷갈린다..

그래도 문제 자체는 내 힘으로 풀었다

github.com/SuyeonChoi/Algorithms/blob/master/BaekJoon/Python/%EC%88%98%ED%95%99/p1456.py