문제 출처 : https://www.acmicpc.net/problem/11502

문제 정리

• 5보다 큰 임의의 홀수를 입력받아서, 그 홀수가 어떻게 세 소수의 합으로 표현될 수 있는지 (또는 불가능한지) 알아보는 프로그램

문제 해결 방법

• 에라토스테네스의 체
  1. 2부터 N까지 모든 수를 써놓는다.
  2. 아직 지워지지 않은 수중에서 가장 작은 수를 찾는다.
  3. 그 수는 소수이다.
  4. 이제 그 수의 배수를 모두 지운다.

코드

• click

코드 설명

에라토스테네스의 체를 사용해서 소수들만 완전 탐색을 하면 된다.

단, 여기서 시간을 줄이기 위해 입력 받은 num 보다 더할 소수가 크면 예외처리 해준다.

"여기서 더 최적화도 가능할 것 같다."

주의사항

그대로 1000 * 1000 * 1000을 하면 10억이라서 시간초과가 발생함