소수의 연속합
면접 대비시간 제한2초메모리 제한128 MB
4,000,000 이하의 정수 N을 연속된 소수들의 합으로 나타내는 방법의 수를 구하는 문제입니다.
문제
자연수 N이 주어진다. N을 하나 이상의 연속된 소수의 합으로 나타내는 방법의 수를 구하시오.
여기서 연속된 소수란 오름차순으로 나열한 소수열에서 서로 이웃해 있는 소수들을 뜻한다. 같은 소수를 두 번 사용할 수 없으며, 중간의 소수를 건너뛴 합은 연속된 소수의 합으로 보지 않는다.
입력
첫째 줄에 자연수 N이 주어진다. (1 <= N <= 4,000,000)
출력
첫째 줄에 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.