C. Primes on Interval（二分 + 前缀和 | 尺取）

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.

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.

Examples

input

Copy

2 4 2

output

Copy

3

input

Copy

6 13 1

output

Copy

4

input

Copy

1 4 3

output

Copy

-1

题意是让你找到一个区间长度l使得任意连续区间的素数个数不小于k。

一开始读错题意了，试了两发Wa。寻找区间内是否满足个数问题，一般前缀和预处理，然后二分枚举区间长度。

二分  + 前缀和

AC Code：

#include<iostream> #include<iomanip> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<string> #include<algorithm> #include<vector> #include<map> #include<stack> #include<queue> #include<deque> #include<set> #include<bitset> #include<cctype> #define LL long long #define maxn (LL)1e6 #define INF 0x3f3f3f3f #define PI acos(-1.0) #define pb push_back #define re register LL const double eps = 0.0000001; using namespace std; typedef pair<LL,LL> pii; inline int sgn(double x) { return (x > eps) - (x < -eps); } LL ans[maxn]; bool res[maxn]; LL sum[maxn]; LL n,m,k; bool judge(int idx)//判断一下是否满足条件 { for(re j = n;j<=m-idx+1;++j) { if(sum[j+idx-1] - sum[j-1]<k) return 0; } return 1; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifndef ONLINE_JUDGE //freopen("input.txt","r",stdin); #endif // ONLINE_JUDGE cin>>n>>m>>k; res[1] = 1; for(re i = 2;i<=sqrt(m);++i)//筛法预处理 { if(!res[i]){ for(re j = 2;i*j<=m;++j) { res[i*j] = 1; } } } sum[n-1] = 0; for(re i= n;i<=m;++i)//前缀和 { sum[i] = sum[i-1] + (res[i]==0?1:0); } if(sum[m]<k) { return cout<<-1,0; } LL L = 1,R = m-n+1; while(L<R)//二分，一开始认为L 不能为1，Wa了一发 { int mid = (R+L)/2; if(judge(mid)) R = mid; else L = mid+1; } cout<<L; }

尺取：

巧妙的狠呐。

比暴力爽的不止一点半点的。

AC Code：  

#include <cstdio> #include <cstring> typedef long long ll; int a,b,k,np=0; int p[1000001]; void mkprime(){//预处理素数 for(int i=2;i<=b;++i) p[i]=1; for(int i=2;i<=b;++i) if(p[i]){ for(ll j=(ll)i*i;j<=b;j+=i) p[j]=0; } } int main() { scanf("%d%d%d",&a,&b,&k); mkprime(); for(int i=a+1;i<=b;++i) p[i]+=p[i-1];//预处理前缀和 p[a-1]=0; if(p[b]<k) puts("-1"); else{ int ans=1,st; for(st=a-1;st+ans<=b;++st)//寻找区间，不满住区间长度增加，前面的都已满足 while(st+ans<=b&&p[st+ans]-p[st]<k) ++ans; printf("%d\n",ans); } return 0; }