1022: Primes on Interval
题目链接：http://acm.zcmu.edu.cn/JudgeOnline/problem.php?id=1022
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 301 Solved: 128
[Submit][Status][Web Board]Description
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
Everay 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 Input
2 4 2
6 13 1
1 4 3
Sample Output
3
4
-1
【题意】满足任意x∈[a, b-l+1]使得[x, x+l-1]至少有k个素数的l的最小取值
【分析】预处理某个数字之前素数的个数，然后查找。
因为数据范围比较大，用一般的素数筛筛不出来，所以要用线性筛。然后查找用二分。
素数筛模板戳这
【代码】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;typedef long long ll;
const int maxn=1e6+10;
int judge[maxn];
int prime[maxn];//存素数
int num[maxn];int a,b,k;void isPrime()//线性筛模板
{int index=0;memset(judge,0,sizeof(judge));for(int i=2;i<maxn;i++){if(judge[i]==0)prime[index++]=i;for(int j=0;j<index&&prime[j]*i<maxn;j++){judge[i*prime[j]]=1;if(i%prime[j]==0)break;}}
}
void init()//预处理个数
{isPrime();memset(num,0,sizeof(num));for(int i=2;i<maxn;i++){if(!judge[i])num[i]=num[i-1]+1;else num[i]=num[i-1];}
}
int check(int x)
{for(int i=a;i<=b-x+1;i++)if(num[i+x-1]-num[i-1]<k)return 0;return 1;
}int main()
{init();while(~scanf("%d%d%d",&a,&b,&k)){int l=1,r=b-a+1,mid,flag=0;while(l<=r){mid=l+(r-l)/2;if(check(mid))r=mid-1,flag=1;else l=mid+1;}if(!flag)puts("-1");else printf("%d\n",l);}return 0;}