지금 소수를 구하는 로직이 각 수에 대해 약수가 2개인지 확인하는 방법인데, 이 방법으로는 수 X의 소수 여부를 O(X)에 판단합니다.
그러면 M = 1, N = 1,000,000일 때 O(N^2)이기 때문에 2초 안에 절대 찾아낼 수 없습니다. 수 X의 소수 여부를 O(루트 X)에 찾아내거나 에라토스테네스의 체를 이용하면 시간 제한 이내로 해결 가능합니다. 이 글의 0x00 챕터를 참고해보세요.
1929번 - 소수 구하기
지금 소수를 구하는 로직이 각 수에 대해 약수가 2개인지 확인하는 방법인데, 이 방법으로는 수 X의 소수 여부를 O(X)에 판단합니다.
그러면 M = 1, N = 1,000,000일 때 O(N^2)이기 때문에 2초 안에 절대 찾아낼 수 없습니다. 수 X의 소수 여부를 O(루트 X)에 찾아내거나 에라토스테네스의 체를 이용하면 시간 제한 이내로 해결 가능합니다. 이 글의 0x00 챕터를 참고해보세요.
댓글을 작성하려면 로그인해야 합니다.
wodus0129 3년 전
다음과 같이 작성했더니 시간초과가 발생합니다.
무엇이 문제인가요?