Problem Primes on Interval (Codeforces)

Link: http://codeforces.com/problemset/problem/237/C

C. Primes on Interval

time limit per test

2 seconds

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 leastk 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 ≤ 10⁶; a ≤ b).

Output

In a single line print a single integer — the required minimum l. If there's no solution, print -1.

Sample test(s)

input

2 4 2

output

3

input

6 13 1

output

4

input

1 4 3

output

-1

Thuật toán:

• Dùng sàn erastosthen sinh các số nguyên tố trong khoảng từ 1..b +10.
• Tính số lượng các số nguyên tố từ 1 đến i : f[i] += f[i-1].
• Dùng tìm kiếm nhị phân tìm kết quả nhỏ nhát thỏa mãn.

code sau của nealzane (thành viên trên codeforces):

#include<cstdio>

#include<iostream>

using namespace std;

int p[2200051];

int a,b,k;

void Prime();

int main()

{

freopen("TEST.INP","r",stdin);

freopen("TEST.OUT","w",stdout);

cin >> a >> b >> k;

Prime();

int res = -1;

int lo = 0, hi = (b - a + 2);

while(lo < hi)

{

int mid = (lo + hi) >> 1;

int find = 1;

for(int x = a - 1; find && x + mid <= b; x++ )

if(p[x + mid] - p[x] < k) find = 0;

if(find)

{

hi = mid;

}  

else

{

lo = mid + 1;

}

} 

cout << (lo > (b - a + 1) ? -1 : lo) << endl;

return 0;

}

void Prime()

{

for(int i = 2; i <= b + 10; i++) p[i] = 1;

for(int i = 2; i <= b + 10; i++)

{

if(p[i]==0) continue;

if(p[i]==1)

{

for(int j = i + i; j <= b + 10; j+=i) p[j] = 0; 

}

}

for(int i = 1; i <= b + 10; i++) p[i] += p[i - 1];

}