시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 19 13 13 68.421%

문제

농부인 존은 연속적인 소수로 소들에게 낙인을 찍기 시작했다. 베시스가 이것을 보았고, 이러한 낙인에 대해서 발생하는 여러가지 자릿수에 대해 궁금증이 생겼다. 베시스를 도와 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자릿수를 포함하는 소수의 갯수를 구한다

예제 입력

10 15 3

예제 출력

1

힌트

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