C. Primes on Interval
链接：
http://codeforces.com/contest/237/problem/C
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <vector> 7 #include <string> 8 #include <map> 9 #include <set> 10 #include <stack> 11 #include <queue> 12 #include <functional> 13 using namespace std; 14 #define rep(i,a,n) for (int i=a;i<=n;i++) 15 #define per(i,a,n) for (int i=n;i>=a;i--) 16 #define pb push_back 17 #define mp make_pair 18 #define all(x) (x).begin(),(x).end() 19 #define fi first 20 #define se second 21 #define SZ(x) ((int)(x).size()) 22 typedef vector<int> VI; 23 typedef long long ll; 24 typedef pair<int, int> PII; 25 const ll mod = 1000000007; 26 // head 27 28 const int maxn = 1e6 + 7; 29 int prime[maxn]; 30 int a, b, k; 31 32 void IsPrime() { 33 prime[0] = prime[1] = 0; prime[2] = 1; 34 for (int i = 3; i<maxn; i++) 35 prime[i] = i % 2 == 0 ? 0 : 1; 36 int t = (int)sqrt(maxn*1.0); 37 for (int i = 3; i <= t; i++) 38 if (prime[i]) 39 for (int j = i*i; j<maxn; j += 2 * i) 40 prime[j] = 0; 41 } 42 43 bool check(int m) { 44 rep(i, a, b - m + 1) if (prime[i + m - 1] - prime[i - 1] < k) return false; 45 return true; 46 } 47 48 int main() 49 { 50 IsPrime(); 51 cin >> a >> b >> k; 52 rep(i, a, b) prime[i] = prime[i - 1] + prime[i]; 53 prime[a - 1] = 0; 54 int l = 1, r = b - a + 1, ans = maxn; 55 while (l <= r) { 56 int mid = (l + r) / 2; 57 if (check(mid)) { 58 r = mid - 1; 59 ans = mid; 60 } 61 else l = mid + 1; 62 } 63 if (ans == maxn) cout << -1 << endl; 64 else cout << ans << endl; 65 return 0; 66 }