시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 4863 1979 1449 41.674%

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

  • 3 : 3 (한 가지)
  • 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
  • 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

2 이상의 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

예제 입력 1

20

예제 출력 1

0

예제 입력 2

3

예제 출력 2

1

예제 입력 3

41

예제 출력 3

3

예제 입력 4

53

예제 출력 4

2
W3sicHJvYmxlbV9pZCI6IjE2NDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMyMThcdWM3NTggXHVjNWYwXHVjMThkXHVkNTY5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NThcdWIwOTggXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWMxOGNcdWMyMThcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOFx1YjRlNFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YmE4NyBcdWFjMDBcdWM5YzAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzU4IFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHViY2Y0XHViYTc0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MyA6IDMgKFx1ZDU1YyBcdWFjMDBcdWM5YzApPFwvbGk+XHJcblx0PGxpPjQxIDogMiszKzUrNysxMSsxMyA9IDExKzEzKzE3ID0gNDEgKFx1YzEzOCBcdWFjMDBcdWM5YzApPFwvbGk+XHJcblx0PGxpPjUzIDogNSs3KzExKzEzKzE3ID0gNTMgKFx1YjQ1MCBcdWFjMDBcdWM5YzApPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjIFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWMxOGNcdWMyMThcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNWM2XHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOFx1YjRlNFx1YjNjNCBcdWM3ODhcdWIyOTRcdWIzNzAsIDIwXHVjNzc0IFx1YWRmOCBcdWM2MDhcdWM3NzRcdWIyZTQuIDcrMTNcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTU4XHViYTc0IDIwXHVjNzc0IFx1YjQxOFx1YWUzMFx1YjI5NCBcdWQ1NThcdWIwOTggN1x1YWNmYyAxM1x1Yzc3NCBcdWM1ZjBcdWMxOGRcdWM3NzQgXHVjNTQ0XHViMmM4XHVhZTMwXHVjNWQwIFx1YzgwMVx1ZDU2OVx1ZDU1YyBcdWQ0NWNcdWQ2MDRcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LiBcdWI2MTBcdWQ1NWMgXHVkNTVjIFx1YzE4Y1x1YzIxOFx1YjI5NCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVkNTVjIFx1YmM4OFx1YjljYyBcdWIzNjdcdWMxNDhcdWM1ZDAgXHVjMGFjXHVjNmE5XHViNDIwIFx1YzIxOCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCAzKzUrNSs3XHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQ0NWNcdWQ2MDRcdWIzYzQgXHVjODAxXHVkNTY5XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG5cclxuPHA+MiBcdWM3NzRcdWMwYzFcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWM3OTBcdWM1ZjBcdWMyMThcdWI5N2MgXHVjNWYwXHVjMThkXHViNDFjIFx1YzE4Y1x1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNzkwXHVjNWYwXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyA0LDAwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3OTBcdWM1ZjBcdWMyMTggTlx1Yzc0NCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHVjMThjXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNjQ0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3VtIG9mIENvbnNlY3V0aXZlIFByaW1lIE51bWJlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPlNvbWUgcG9zaXRpdmUgaW50ZWdlcnMgY2FuIGJlIHJlcHJlc2VudGVkIGJ5IGEgc3VtIG9mIG9uZSBvciBtb3JlIGNvbnNlY3V0aXZlIHByaW1lIG51bWJlcnMuIEhvdyBtYW55IHN1Y2ggcmVwcmVzZW50YXRpb25zIGRvZXMgYSBnaXZlbiBwb3NpdGl2ZSBpbnRlZ2VyIGhhdmU/IEZvciBleGFtcGxlLCB0aGUgaW50ZWdlciA1MyBoYXMgdHdvIHJlcHJlc2VudGF0aW9ucyA1ICsgNyArIDExICsgMTMgKyAxNyBhbmQgNTMuIFRoZSBpbnRlZ2VyIDQxIGhhcyB0aHJlZSByZXByZXNlbnRhdGlvbnMgMiArIDMgKyA1ICsgNyArIDExICsgMTMsIDExICsgMTMgKyAxNywgYW5kIDQxLiBUaGUgaW50ZWdlciAzIGhhcyBvbmx5IG9uZSByZXByZXNlbnRhdGlvbiwgd2hpY2ggaXMgMy4gVGhlIGludGVnZXIgMjAgaGFzIG5vIHN1Y2ggcmVwcmVzZW50YXRpb25zLiBOb3RlIHRoYXQgc3VtbWFuZHMgbXVzdCBiZSBjb25zZWN1dGl2ZSBwcmltZSBudW1iZXJzLCBzbyBuZWl0aGVyIDcgKyAxMyBub3IgMyArIDUgKyA1ICsgNyBpcyBhIHZhbGlkIHJlcHJlc2VudGF0aW9uIGZvciB0aGUgaW50ZWdlciAyMC48XC9wPlxyXG5cclxuPHA+WW91ciBtaXNzaW9uIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IHJlcG9ydHMgdGhlIG51bWJlciBvZiByZXByZXNlbnRhdGlvbnMgZm9yIHRoZSBnaXZlbiBwb3NpdGl2ZSBpbnRlZ2VyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGlzIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIuJm5ic3A7VGhlIGludGVnZXJzIGFyZSBiZXR3ZWVuIDEmbmJzcDthbmQgNCwwMDAsMDAwLCBpbmNsdXNpdmUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+QW4gb3V0cHV0IGxpbmUgaW5jbHVkZXMgdGhlIG51bWJlciBvZiByZXByZXNlbnRhdGlvbnMgZm9yIHRoZSBpbnB1dCBpbnRlZ2VyIGFzIHRoZSBzdW0gb2Ygb25lIG9yIG1vcmUgY29uc2VjdXRpdmUgcHJpbWUgbnVtYmVycy4gTm8gb3RoZXIgY2hhcmFjdGVycyBzaG91bGQgYmUgaW5zZXJ0ZWQgaW4gdGhlIG91dHB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > Japan > Asia Regional Contest 2005 in Tokyo A번

  • 문제를 번역한 사람: author5
  • 문제의 오타를 찾은 사람: d252b