wodus0129   3년 전

다음과 같이 작성했더니 시간초과가 발생합니다.

무엇이 문제인가요?

지금 소수를 구하는 로직이 각 수에 대해 약수가 2개인지 확인하는 방법인데, 이 방법으로는 수 X의 소수 여부를 O(X)에 판단합니다.

그러면 M = 1, N = 1,000,000일 때 O(N^2)이기 때문에 2초 안에 절대 찾아낼 수 없습니다. 수 X의 소수 여부를 O(루트 X)에 찾아내거나 에라토스테네스의 체를 이용하면 시간 제한 이내로 해결 가능합니다. 이 글의 0x00 챕터를 참고해보세요.

댓글을 작성하려면 로그인해야 합니다.