wiz   8년 전

에라토스테네스의 체를 이용해 미리 소수를 구해놓고

작동 시키려는데 메모리 초과가 뜨네요.

제 생각엔 미리 소수인지 아닌지 구해놓아야 시간초과가 생기지 않을거 같은데...

다른 방식이 있는 건지 궁금합니다.

답변 부탁드립니다.

baekjoon   8년 전

첫 자리는 2, 3, 5, 7로 시작해야 하고, 또 그 다음 자리의 경우의 수도 계속해서 줄어들기 때문에, 에라토스테네스의 체를 사용하지 않는 것이 시간이나 메모리가 더 절약됩니다.

wiz   8년 전

말씀하신대로 하니 쉽게 풀렸네요.

늦었지만 답변 감사합니다.

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