에라토스테네스의 체 (소수 찾기)

from. 백준 4948번: 베르트랑 공준 (solved)

2021/12/10

이 문제는 우선적으로 '소수 찾기' 알고리즘을 써야 한다.

소수 찾기 하면 에라토스테네스의 체를 사용해야 하지 않겠는가.

마음 편하게 

이런식으로 돌려봤었다. 하지만 어라라 시간 초과가 떴다. 비슷하게는 풀리는데, 비효율적인 것 같다. 

조금 찾아본 결과 내 생각에는 에라토스테네스의 체에서 알고리즘을 조금 바꿔야 할 것 같다. 

우선 더 고민해본다.

-----------------------

2021/12/11

결국 다른 식으로 풀어봤다. 

우선적으로, n의 value를 수 제한이었던 123456의 2배로 늘렸다. 2n까지 계산해야 하니깐!

그리고 처음에 primes라는 list를 만들어서 n부터 2n까지의 숫자가 존재하는지를 따지는 것은 O(n)의 시간이 걸리는 비효율적인 알고리즘이라는 것을 파악하고, 따로 Prime인지 아닌지를 나타내는 list인 a를 만들어서 에라토스테네스의 체 알고리즘을 사용했다.

근데, 여기서 처음에 Prime을 Search 할때도 범위를 2부터 루트n까지로 찾았는데, 루트n까지만 찾아도 모든 수들을 찾을 수 있기 때문이다. 

 

Cool!