2 seconds
256 megabytes
standard input
standard output
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.
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.
A single line contains three space-separated integers a, b, k (1 ≤ a, b, k ≤ 106; a ≤ b).
In a single line print a single integer — the required minimum l. If there's no solution, print -1.
2 4 2
3
6 13 1
4
1 4 3
-1
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = ;
#define inf (1<<29)
// p[i] is i-th prime's position
bool pp[maxn];
int p[maxn] , cnt = ;
int ss[maxn] , tt[maxn];
void init() {
cnt = ;
pp[] = pp[] = ;
tt[] = tt[] = -;
for(int i=;i<maxn;i++) {
if(!pp[i]) {
p[cnt++] = i;
for(int j=i+i;j<maxn;j+=i) {
pp[j] = true;
}
}
tt[i] = cnt - ;
}
for(int i=;i<maxn;i++) {
if(!pp[i]) ss[i] = tt[i];
else ss[i] = tt[i] + ;
}
}
int main() {
init();
int a , b , k;
while(~scanf("%d%d%d" , &a,&b,&k)) {
int s = ss[a] , t = tt[b];
int num = t - s + ;
//printf("debug:\n");
//printf("s is %d , t is %d\n" , s , t);
//printf("first pri is %d , last prime is %d\n" , p[s] , p[t]);
if(num < k) {
printf("-1\n");
continue;
}
int ans = ;
int tmp;
tmp = b - p[t-k+] + ;
if(tmp > ans) ans = tmp;
tmp = p[s+k-] - a + ;
if(tmp > ans) ans = tmp;
for(int i=s;i+k<=t;i++) {
tmp = p[i+k] - p[i];
if(tmp > ans) ans = tmp;
}
printf("%d\n" , ans);
}
return ;
}