[Python] 백준 1929 소수 구하기 (에라토스테네스의 체 vs 시간초과)

소수 구하기 문제

 

 

시간초과를 고려하지 않고 짠 코드

 

처음에는 시간초과를 고려하지 않고 중첩 반복문을 사용하여 간단하게 해결 할 수

있다고 생각했다. 1부터 1,000,000 사이의 수(1<=M<=N<=1,000,000)를 하나씩

다 확인하려니 시간초과가 발생하는 것은 당연한 결과였다.  

 

 

문제해결을 위해 문제에서 제시되어있는 에라토스테네스의 체를 활용하기로 하였다.

에라토스테네스의 체란 일정 범위내 수열에서 배수들을 제거해 소수만 남기는 방법이다.

 

 

 

 

 

ex) 수열 [2 3 4 5 6 7 8 9 10] 에서 2의 배수 제거

=> [2 3 5 7 9] 에서 3의 배수 제거

=> [2 3 5 7]

말그대로 체로 걸러서 소수만 남기는 게 핵심이다.

 

 

시간초과 해결을 위해 수정한 코드

 

앞으로 범위내의 소수를 구할때에는 에라토스테네스의 체를 이용해야겠다.