백준1929 파이썬 python (에라토스테네스의 체, 시간복잡도)

문제 풀이

간단한 소수구하기 문제이다.
M과 N의 범위를 지정해서 for문을 돌리면서 (돌리는 값을 i)라고 생각했을 때
i값이 소수인지 다시 for문을 돌리면 되는 브루투포스문제이다.

코드 1

다음과 같은 코드로 작성을 했더니 시간초과가 났다.

코드 2

에라토스테네스의 체를 이용해 소수를 구했다.
에라토스테네스에 대해서 알아보자면
범위를 2부터 (i**0.5)+1까지 돌면서 특정 수의 제곱근을 구해 그 제곱근의 약수를 포함하는 수를 모두 제거하는 규칙이다. 나누어 떨어지는 약수가 존재할 경우 그 제곱근 이상의 숫자를 검사하지 않아도 되어 시간복잡도를 향상 시킬 수 있다.

시간복잡도 해결

코드 1의 방식으로는 O(N)으로 for문을 무자비하게 돌리는 방식이였지만
제거를 해나가면서 검사할 부분만 검사하게된다면 검사할 범위값이 줄어들어 O(N)->O(N^(1/2))가 되어 시간초과 늪에서 해결할 수 있었다.

문제출처 : https://www.acmicpc.net/problem/1929