ekdrn1   2년 전

에라스토테네스의 체로 소수 구했다고 다가 아니네요...


가장 먼저 떠오르는 방법이

1. 인풋값을 저장한다.

2. 체를 활용해 소수를 구한다.

3. 이중루프 돌면서 두 소수의 합과 (다시 루프 또 돌면서)인풋값을 비교한다. 

일 텐데,

이대로 해선 시간초과 나오네요. 3번의 O(N^2 * M) 시간복잡도를 어떻게든 낮추는 것이 이 문제의 핵심 키포인트입니다.


질문게시판에서 얻은 핵심 힌트는 (인풋값 - 소수) 의 결과값이 소수인가(bool)?를 확인하는 것이었습니다. 

어디선가 bool값 모아놓은거 구해놨었잖아요?

단순하게 생각했다가 10회제출하고 고통받았네요 ㅠㅠ

저처럼 고통받으시는분들 약간의 실마리라도 얻으시라고 올려봅니다.

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