1929번 - 소수 구하기
에라토스테네스의 체 알고리즘 활용해서 풀었는데 시간초과가 뜨네요 어떻게 시간을 줄일수있을까요?
에라토스테네스의 체를 쓰시지 않았습니다.
해당 개념을 다시한번 확인해보시구 에라토스테네스의 체를 적용해서 다시 풀어보세요!
현재는 시간복잡도가 O(N^2) 입니다.
에라토스테네스의 체 사용 시 O(Nsqrt(N))으로 가능합니다.
에라토스테네스의 체 시간복잡도는 O(NlglgN) 입니다
댓글을 작성하려면 로그인해야 합니다.
ekgus0813 1년 전
에라토스테네스의 체 알고리즘 활용해서 풀었는데 시간초과가 뜨네요 어떻게 시간을 줄일수있을까요?