jupiny   3년 전

에라토스테네스의 체와 부분합을 이용하여 문제를 풀었습니다.

예제에 나오는 입력은 모두 잘 통과하지만 제출하면 바로 틀렸다고 나타나네요 ㅠㅠ

아래 코드의 틀린 이유를 찾아주시면 정말 감사하겠습니다!!

RiKang   3년 전

prime 에 sqrt(MAX_N) 이하인 소수만 들어가 있어서

입력으로 큰 소수 (3999971 같은?)가 들어왔을 때 답이 1인데 0으로 나오는 듯 합니다.

jupiny   3년 전

감사합니다!

말씀해주신대로 prime이라는 vector에 sqrt(MAX_N) 보다 큰 소수는 안 들어가고 있었네요 ㅠㅠ

그 부분과 아래의 부분합 계산하는 부분의 시간복잡도를 바꾸어 해결했습니다 :D

(혹시나 싶어 3999971을 돌려보니 2가 나오더군요. 아마 한 가지 경우가 더 있나봅니다 ㅎㅎ)

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