qwer9412   3일 전

에라토스테네스의 체로 소수를 모두 구하는데 1초가 안걸리고 10000000이하 소수는 400여개여서 시간초과가 안날줄 알았는데 시간초과가 나네요 ㅠㅠ

혹시 왜 그런지 설명해 주실분 계실까요..?

rlarla97   3일 전

1. 10,000,000 이하의 소수가 전부 들어가 있는 코드가 아닙니다. 또한 소수 구하는 방법 자체도 primeVisit의 flag에 따라 for - j 를 반복여부를 정할 수 있는데, 그렇지 않고 모두 for문을 돌려버리니 mapPrime()에서 시간초과가 나버립니다.

2. primeVisit으로 소수를 구하신 것을 다시 primes 리스트에 모두 넣고 다시 빼내기 때문에 그만큼의 오버헤드가 더 발생합니다.

3. 반복문 출력부분에서도 리스트를 반복적으로 로드하여 요소를 빼냅니다. 이또한 불필요한 오버헤드 비용이 큽니다.

qwer9412   3일 전

두 분 모두 답변 감사합니다!

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