시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 61 44 37 72.549%

문제

농부 존은 소들에게 소수로 차례차례 번호를 매기는 중이다. 베시는 이 번호에서 숫자 D가 몇 번이나 등장하는지 궁금해졌다.

베시를 도와 범위 A..B(A와 B 포함)내에서 숫자 D를 포함하는 소수의 개수를 구해보자.

소수는 두개의 자연수(1과 자기자신)로만 나누어 떨어지는 자연수를 말한다. 소수의 예로는 2,3,5,7,11,13,17,19,23,29.. 가 있다.

입력

세 정수 A, B, D가 주어진다.

출력

주어진 범위 내에서 숫자 D를 포함하는 소수의 개수를 출력한다.

제한

  • 1 ≤ A ≤ B ≤ 4,000,000
  • B ≤ A + 2,000,000

예제 입력 1

10 15 3

예제 출력 1

1

힌트

13은 범위 3안에 들어있다.

W3sicHJvYmxlbV9pZCI6IjYyMTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMyMThcdWM3NTggXHVjNzkwXHVhY2E5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIxOGRcdWJkODAgXHVjODc0XHVjNzQwIFx1YzE4Y1x1YjRlNFx1YzVkMFx1YWM4YyBcdWMxOGNcdWMyMThcdWI4NWMgXHVjYzI4XHViODQwXHVjYzI4XHViODQwIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWI5ZTRcdWFlMzBcdWIyOTQgXHVjOTExXHVjNzc0XHViMmU0LiBcdWJjYTBcdWMyZGNcdWIyOTQgXHVjNzc0IFx1YmM4OFx1ZDYzOFx1YzVkMFx1YzExYyBcdWMyMmJcdWM3OTAgRFx1YWMwMCBcdWJhODcgXHViYzg4XHVjNzc0XHViMDk4IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWM4NGNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmNhMFx1YzJkY1x1Yjk3YyBcdWIzYzRcdWM2NDAgXHViYzk0XHVjNzA0IEEuLkIoQVx1YzY0MCBCIFx1ZDNlY1x1ZDU2OClcdWIwYjRcdWM1ZDBcdWMxMWMgXHVjMjJiXHVjNzkwIERcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHViMjk0IFx1YzE4Y1x1YzIxOFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWMxOGNcdWMyMThcdWIyOTQgXHViNDUwXHVhYzFjXHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOCgxXHVhY2ZjIFx1Yzc5MFx1YWUzMFx1Yzc5MFx1YzJlMClcdWI4NWNcdWI5Y2MgXHViMDk4XHViMjA0XHVjNWI0IFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMThcdWI5N2MgXHViOWQwXHVkNTVjXHViMmU0LiBcdWMxOGNcdWMyMThcdWM3NTggXHVjNjA4XHViODVjXHViMjk0IDIsMyw1LDcsMTEsMTMsMTcsMTksMjMsMjkuLiBcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjMTM4IFx1YzgxNVx1YzIxOCBBLCBCLCBEXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4ZmNcdWM1YjRcdWM5YzQgXHViYzk0XHVjNzA0IFx1YjBiNFx1YzVkMFx1YzExYyBcdWMyMmJcdWM3OTAgRFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHVjMThjXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPGEgaWQ9XCJjb21tZW50LTQ3MjA3XCI+PFwvYT48XC9wPlxyXG4iLCJoaW50IjoiPHA+MTNcdWM3NDAgXHViYzk0XHVjNzA0IDNcdWM1NDhcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0IiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBBICZsZTsgQiAmbGU7IDQsMDAwLDAwMDxcL2xpPlxyXG5cdDxsaT5CICZsZTsgQSArIDIsMDAwLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiNjIxOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlF1YWxpZmllZCBQcmltZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huIGhhcyBiZWd1biBicmFuZGluZyB0aGUgY293cyB3aXRoIHNlcXVlbnRpYWwgcHJpbWUgbnVtYmVycy4gQmVzc2llIGhhcyBub3RpY2VkIHRoaXMgYW5kIGlzIGN1cmlvdXMgYWJvdXQgdGhlIG9jY3VycmVuY2Ugb2YgdmFyaW91cyBkaWdpdHMgaW4gdGhvc2UgYnJhbmRzLjxiciBcLz5cclxuJm5ic3A7PGJyIFwvPlxyXG5IZWxwIEJlc3NpZSBkZXRlcm1pbmUgdGhlIG51bWJlciBvZiBwcmltZXMgaW4gdGhlIGluY2x1c2l2ZSByYW5nZSBBLi5CICgxICZsdDs9IEEgJmx0Oz0gQiAmbHQ7PSA0LDAwMCwwMDA7IEIgJmx0Oz0gQSArIDEsMDAwLDAwMDsgb25lIHRlc3QgY2FzZSBoYXMgQiAmbHQ7PSBBICsgMiwwMDAsMDAwICkgdGhhdCBjb250YWluIGEgc3VwcGxpZWQgZGlnaXQgRC48XC9wPlxyXG5cclxuPHA+QSBwcmltZSBpcyBhIHBvc2l0aXZlIGludGVnZXIgd2l0aCBleGFjdGx5IHR3byBkaXZpc29ycyAoMSBhbmQgaXRzZWxmKS4gVGhlIGZpcnN0IHByaW1lcyBhcmUgMiwgMywgNSwgNywgMTEsIDEzLCAxNywgMTksIDIzLCBhbmQsIDI5LjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogQSwgQiwgYW5kIEQ8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaGUgY291bnQgb2YgcHJpbWVzIGluIHRoZSByYW5nZSB0aGF0IGNvbnRhaW4gdGhlIGRpZ2l0IEQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiPHA+SnVzdCAxMyBpbiB0aGlzIHJhbmdlIGNvbnRhaW5zIGEgJiMzOTszJiMzOTsuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=