codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```