Algorithm


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 aa + 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 xx + 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 ≤ 106a ≤ 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



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <stdio.h>

using namespace std;

int const N = 1e6 + 1;
int a, b, k, cs[N];
bool prime[N];

void sieve() {
	memset(prime, true, sizeof prime);
	prime[0] = prime[1] = false;

	for(int i = 2; i * i < N; ++i)
		if(prime[i])
			for(int j = i * i; j < N; j += i)
				prime[j] = false;

	cs[0] = 0;
	for(int i = 1; i <= N; ++i)
		cs[i] = cs[i - 1] + prime[i - 1];
}

bool can(int mid) {
	for(int i = a; i <= b - mid + 1; ++i)
		if(cs[i + mid] - cs[i] < k)
			return false;
	return true;
}

int main() {
	sieve();

	scanf("%d %d %d", &a, &b, &k);

	int l = 1, r = b - a + 1, mid, res = -1;
	while(l <= r) {
		mid = (l + r) >> 1;
		if(can(mid)) {
			r = mid - 1;
			res = mid;
		} else
			l = mid + 1;
	}

	printf("%d\n", res);

    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
2 4 2

Output

x
+
cmd
3
Advertisements

Demonstration


Codeforcess Solution  Primes on Interval, C. Primes on Interval ,C,C++, Java, Js and Python , Primes on Interval,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+