https://www.acmicpc.net/problem/1644

에라토스테네스의 체로 우선 400만 이하의 모든 소수를 찾아낸다음, 정직하게 합을 찾아 N과 같은 경우의 갯수를 구하면 됩니다. 에라토스테네스의 시간복잡도가 O(NlgN)이므로 자칫하면 시간 초과가 발생할 것 같았는데 생각보다 꽤 빠르게 연산이 이루어졌습니다.(32ms)

https://github.com/encrypted-def/BOJ/blob/master/1644.cpp