C. Primes on Interval
time limit per test
2 secondsmemory limit per test
256 megabytesinput
standard inputoutput
standard outputYou'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.
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.
Find and print the required minimum l. If no value l meets the described limitations, print -1.
Input
A single line contains three space-separated integers a, b, k (1 ≤ a, b, k ≤ 106; a ≤ b).
Output
In a single line print a single integer — the required minimum l. If there's no solution, print -1.
Sample test(s)
input
2 4 2
output
3
input
6 13 1
output
4
input
1 4 3
output
-1
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 1001000; 7 #define inf (1<<29) 8 // p[i] is i-th prime's position 9 bool pp[maxn]; 10 int p[maxn] , cnt = 0; 11 int ss[maxn] , tt[maxn]; 12 void init() { 13 cnt = 0; 14 pp[0] = pp[1] = 1; 15 tt[0] = tt[1] = -1; 16 for(int i=2;i<maxn;i++) { 17 if(!pp[i]) { 18 p[cnt++] = i; 19 for(int j=i+i;j<maxn;j+=i) { 20 pp[j] = true; 21 } 22 } 23 tt[i] = cnt - 1; 24 } 25 for(int i=0;i<maxn;i++) { 26 if(!pp[i]) ss[i] = tt[i]; 27 else ss[i] = tt[i] + 1; 28 } 29 } 30 int main() { 31 init(); 32 int a , b , k; 33 while(~scanf("%d%d%d" , &a,&b,&k)) { 34 int s = ss[a] , t = tt[b]; 35 int num = t - s + 1; 36 //printf("debug: "); 37 //printf("s is %d , t is %d " , s , t); 38 //printf("first pri is %d , last prime is %d " , p[s] , p[t]); 39 if(num < k) { 40 printf("-1 "); 41 continue; 42 } 43 int ans = 0; 44 int tmp; 45 tmp = b - p[t-k+1] + 1; 46 if(tmp > ans) ans = tmp; 47 tmp = p[s+k-1] - a + 1; 48 if(tmp > ans) ans = tmp; 49 for(int i=s;i+k<=t;i++) { 50 tmp = p[i+k] - p[i]; 51 if(tmp > ans) ans = tmp; 52 } 53 printf("%d " , ans); 54 } 55 return 0; 56 }