시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 59 43 36 73.469%

문제

농부인 존은 연속적인 소수로 소들에게 낙인을 찍기 시작했다. 베시스가 이것을 보았고, 이러한 낙인에 대해서 발생하는 여러가지 자릿수에 대해 궁금증이 생겼다. 베시스를 도와 A와 B 사이에 발생하는 D자릿수를 포함하는 소수를 구하라 (1 <= A <= B <= 4,000,000; B <= A + 1,000,000; 한개의 케이스에 대하여 B <= A + 2,000,000 )

소수란 양의 정수로 두개의 숫자로만 나누어진다(1과 자기 자신). 처음 소수는 2,3,5,7,11,13,17,23, 그리고 29이다.

입력

세 개의 정수가 공백으로 분리되어 입력 된다: A,B,D

출력

주어진 범위 안에 D자릿수를 포함하는 소수의 갯수를 구한다

예제 입력 1

10 15 3

예제 출력 1

1

힌트

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

W3sicHJvYmxlbV9pZCI6IjYyMTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMyMThcdWM3NTggXHVjNzkwXHVhY2E5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIxOGRcdWJkODBcdWM3NzggXHVjODc0XHVjNzQwIFx1YzVmMFx1YzE4ZFx1YzgwMVx1Yzc3OCBcdWMxOGNcdWMyMThcdWI4NWMgXHVjMThjXHViNGU0XHVjNWQwXHVhYzhjIFx1YjA5OVx1Yzc3OFx1Yzc0NCBcdWNjMGRcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTg4XHViMmU0LiBcdWJjYTBcdWMyZGNcdWMyYTRcdWFjMDAgXHVjNzc0XHVhYzgzXHVjNzQ0IFx1YmNmNFx1YzU1OFx1YWNlMCwmbmJzcDtcdWM3NzRcdWI3ZWNcdWQ1NWMgXHViMDk5XHVjNzc4XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWJjMWNcdWMwZGRcdWQ1NThcdWIyOTQgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwIFx1Yzc5MFx1YjliZlx1YzIxOFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhZDgxXHVhZTA4XHVjOTlkXHVjNzc0IFx1YzBkZFx1YWNiY1x1YjJlNC4gXHViY2EwXHVjMmRjXHVjMmE0XHViOTdjIFx1YjNjNFx1YzY0MCBBXHVjNjQwIEIgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YmMxY1x1YzBkZFx1ZDU1OFx1YjI5NCBEXHVjNzkwXHViOWJmXHVjMjE4XHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCZuYnNwO1x1YzE4Y1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWI3N2MmbmJzcDsoMSAmbHQ7PSBBICZsdDs9IEIgJmx0Oz0gNCwwMDAsMDAwOyBCICZsdDs9IEEgKyAxLDAwMCwwMDA7IFx1ZDU1Y1x1YWMxY1x1Yzc1OCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTU4XHVjNWVjJm5ic3A7QiAmbHQ7PSBBICsgMiwwMDAsMDAwICk8XC9wPlxyXG5cclxuPHA+XHVjMThjXHVjMjE4XHViNzgwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHViNDUwXHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWIwOThcdWIyMDRcdWM1YjRcdWM5YzRcdWIyZTQoMVx1YWNmYyBcdWM3OTBcdWFlMzAgXHVjNzkwXHVjMmUwKS4gXHVjYzk4XHVjNzRjIFx1YzE4Y1x1YzIxOFx1YjI5NCAyLDMsNSw3LDExLDEzLDE3LDIzLCZuYnNwO1x1YWRmOFx1YjlhY1x1YWNlMCAyOVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1YzEzOCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWJkODRcdWI5YWNcdWI0MThcdWM1YjQgXHVjNzg1XHViODI1IFx1YjQxY1x1YjJlNDogQSxCLEQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4ZmNcdWM1YjRcdWM5YzQgXHViYzk0XHVjNzA0IFx1YzU0OFx1YzVkMCBEXHVjNzkwXHViOWJmXHVjMjE4XHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWMxOGNcdWMyMThcdWM3NTggXHVhYzJmXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1Y1x1YjJlNDxcL3A+XHJcbiIsImhpbnQiOiI8cD4xM1x1Yzc0MCBcdWJjOTRcdWM3MDQgM1x1YzU0OFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2MjE5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUXVhbGlmaWVkIFByaW1lcyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaGFzIGJlZ3VuIGJyYW5kaW5nIHRoZSBjb3dzIHdpdGggc2VxdWVudGlhbCBwcmltZSBudW1iZXJzLiBCZXNzaWUgaGFzIG5vdGljZWQgdGhpcyBhbmQgaXMgY3VyaW91cyBhYm91dCB0aGUgb2NjdXJyZW5jZSBvZiB2YXJpb3VzIGRpZ2l0cyBpbiB0aG9zZSBicmFuZHMuPGJyIFwvPlxyXG4mbmJzcDs8YnIgXC8+XHJcbkhlbHAgQmVzc2llIGRldGVybWluZSB0aGUgbnVtYmVyIG9mIHByaW1lcyBpbiB0aGUgaW5jbHVzaXZlIHJhbmdlIEEuLkIgKDEgJmx0Oz0gQSAmbHQ7PSBCICZsdDs9IDQsMDAwLDAwMDsgQiAmbHQ7PSBBICsgMSwwMDAsMDAwOyBvbmUgdGVzdCBjYXNlIGhhcyBCICZsdDs9IEEgKyAyLDAwMCwwMDAgKSB0aGF0IGNvbnRhaW4gYSBzdXBwbGllZCBkaWdpdCBELjxcL3A+XHJcblxyXG48cD5BIHByaW1lIGlzIGEgcG9zaXRpdmUgaW50ZWdlciB3aXRoIGV4YWN0bHkgdHdvIGRpdmlzb3JzICgxIGFuZCBpdHNlbGYpLiBUaGUgZmlyc3QgcHJpbWVzIGFyZSAyLCAzLCA1LCA3LCAxMSwgMTMsIDE3LCAxOSwgMjMsIGFuZCwgMjkuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBBLCBCLCBhbmQgRDxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFRoZSBjb3VudCBvZiBwcmltZXMgaW4gdGhlIHJhbmdlIHRoYXQgY29udGFpbiB0aGUgZGlnaXQgRC48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiI8cD5KdXN0IDEzIGluIHRoaXMgcmFuZ2UgY29udGFpbnMgYSAmIzM5OzMmIzM5Oy48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==