6061: 质数

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:40 Solved:45

Description

农夫约翰开始用连续质数给奶牛烙上记号。Bessie注意到这一点并且对这些质数烙印中的数字比较挑剔。 帮助Bessie确定在范围A..B(1 <= A <= B <= 4,000,000; B <= A + 1,000,000; 有一个测试点B <= A + 2,000,000 ) 包含一个特定的数字D。
 一个质数是一个正整数且只有两个约数(1和它本身)。一开始的质数是2, 3, 5, 7, 11, 13, 17, 19, 23和29。

Input

一行:三个用空格隔开的整数:A, B和D

Output

一行:包含数字D的质数个数。

Sample Input Copy

10 15 3

Sample Output Copy

1