codeforce --- 237C

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 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.

Sample test(s)
input
2 4 2
output
3
input
6 13 1
output
4
input
1 4 3
output
-1

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn = 1001000;
 7 #define  inf (1<<29)
 8 // p[i] is i-th prime's position
 9 bool pp[maxn];
10 int p[maxn] , cnt = 0;
11 int ss[maxn] , tt[maxn];
12 void init() {
13     cnt = 0;
14     pp[0] = pp[1] = 1;
15     tt[0] = tt[1] = -1;
16     for(int i=2;i<maxn;i++) {
17         if(!pp[i]) {
18             p[cnt++] = i;
19             for(int j=i+i;j<maxn;j+=i) {
20                 pp[j] = true;
21             }
22         }
23         tt[i] = cnt - 1;
24     }
25     for(int i=0;i<maxn;i++) {
26         if(!pp[i]) ss[i] = tt[i];
27         else ss[i] = tt[i] + 1;
28     }
29 }
30 int main() {
31     init();
32     int a , b , k;
33     while(~scanf("%d%d%d" , &a,&b,&k)) {
34         int s = ss[a] , t = tt[b];
35         int num = t - s + 1;
36         //printf("debug:
");
37         //printf("s is %d , t is %d
" , s , t);
38         //printf("first pri is %d , last prime is %d
" , p[s] , p[t]);
39         if(num < k) {
40             printf("-1
");
41             continue;
42         }
43         int ans = 0;
44         int tmp;
45         tmp = b - p[t-k+1] + 1;
46         if(tmp > ans) ans = tmp;
47         tmp = p[s+k-1] - a + 1;
48         if(tmp > ans) ans = tmp;
49         for(int i=s;i+k<=t;i++) {
50             tmp = p[i+k] - p[i];
51             if(tmp > ans) ans = tmp;
52         }
53         printf("%d
" , ans);
54     }
55     return 0;
56 }
原文地址:https://www.cnblogs.com/anhuizhiye/p/3603583.html