237C.md (1196B)
1 Source: https://codeforces.com/problemset/problem/237/C 2 3 C. Primes on Interval 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 You've decided to carry out a survey in the theory of prime numbers. Let us remind you that a prime number is a positive integer that has exactly two distinct positive integer divisors. 22 23 Consider positive integers *a*, *a* + 1, ..., *b* (*a* ≤ *b*). You want to find the minimum integer *l* (1 ≤ *l* ≤ *b* - *a* + 1) such that for any integer *x* (*a* ≤ *x* ≤ *b* - *l* + 1) among *l* integers *x*, *x* + 1, ..., *x* + *l* - 1 there are at least *k* prime numbers. 24 25 Find and print the required minimum *l*. If no value *l* meets the described limitations, print -1. 26 27 Input 28 29 A single line contains three space-separated integers *a*, *b*, *k* (1 ≤ *a*, *b*, *k* ≤ 106; *a* ≤ *b*). 30 31 Output 32 33 In a single line print a single integer — the required minimum *l*. If there's no solution, print -1. 34 35 Examples 36 37 Input 38 39 ``` 40 2 4 2 41 ``` 42 43 Output 44 45 ``` 46 3 47 ``` 48 49 Input 50 51 ``` 52 6 13 1 53 ``` 54 55 Output 56 57 ``` 58 4 59 ``` 60 61 Input 62 63 ``` 64 1 4 3 65 ``` 66 67 Output 68 69 ``` 70 -1 71 ```