【CodeForces】237C - Primes on Interval（二分）

题目链接：点击打开题目

C. Primes on Interval

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

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.

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

2 4 2

output

3

input

6 13 1

output

4

input

1 4 3

output

-1

这题绕的不行，但是还是能观察出来，l 越大越容易成立，要求的是最小的 l ，那么就二分好了。

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
#define MAX 1000000 
int pr[MAX+11] = {1,1};
int cnt[MAX+11];
int a,b,k;
void GetPrime()
{
	for (int i = 2 ; i <= 500000 ; i++)
	{
		if (!pr[i])
			for (int j = i + i ; j <= MAX ; j += i)
				pr[j] = 1;
	}
	cnt[0] = 0;
	for (int i = 1 ; i <= MAX ; i++)
		cnt[i] = cnt[i-1] + (!pr[i]);		//素数个数前缀和 
}
bool check(int mid)
{
	for (int i = a ; i <= b - mid + 1 ; i++)
	{
		if (cnt[i+mid-1] - cnt[i-1] < k)
			return false;
	}
	return true;
}
int main()
{
	GetPrime();
	while (~scanf ("%d %d %d",&a,&b,&k))
	{
		int l = 1;
		int r = b-a+1;
		int mid;
		while (r >= l)
		{
			mid = (r + l) >> 1;
			if (check(mid))
				r = mid - 1;
			else
				l = mid + 1;
		}
		if (l <= b-a+1)		//范围内有满足的答案 
			printf ("%d\n",l);
		else
			puts("-1");
	}
	return 0;
}