free0122   11일 전

이런거 저런거 다해봤는데도 시간초과가 뜨네요. ㅠㅠ

 어떻게 더 빠르게 할까요?

movegreen   11일 전

일단 ii 들어간 for문에 i*(0.5)라 되어있습니다. 에라토스테네스 체가 O(n^1/2)인데 지금 코드는 O(n^2)인거 같습니다. 혹시 몰라서 작성자분이 다른 소수 문제를 푸신게 있나 봤고, 소수구하기 문제 코드가 있길레 봤습니다만, 지금 아예 핵심을 이해하지 못하신거 같습니다. 5700ms 걸릴게 아닙니다. 300~400ms 안으로 나와야 에라토스테네스 체를 썼다고 볼 수 있는데, O(n^3/2)로 구하셔서 그런 것으로 보입니다.

간단하게 말씀드리자면, 소수 구하는 알고리즘을 제대로 이해하지 못하셨고, 비슷하게 짜려고 하신거 같습니다만 시간이 오버될 수 밖에 없는 구조로 짜셨습니다.

free0122   11일 전

movegreen

답변해 주셔서 감사합니다!

이번 기회에 다시 공부를 해보겠습니다!

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