POJ ( acm.pku.edu.cn ) 3518

我挺自我欣赏那二分查找的算法

#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;
typedef unsigned int uint;
uint primes[100001];
struct init {
 init() {
     primes[0]=2;
     bool ok=true;
     int n=1;
     uint p;
     for (uint i=3;n<=100000;i+=2) {
         ok=true;
         uint sq=sqrt(double(i))+1;
         for (uint j=1;j<n;++j) {
             p=primes[j];
             if (p>sq)   {
                 ok=true;
                 break;
             }
             if (i%p==0) {
                 ok=false;
                 break;
             }
         }
         if (ok) {
             primes[n]=i;
             ++n;
         }
     }
 }
}initer;

template <class T>
size_t bin_search(T* array, size_t len, T const& n) {
 size_t a=0,b=len,m1,m2=-1;
 for (m1=(a+b)>>1;m1!=m2;) {
     m2=m1;
     if     (array[m1]==n) return m1;
     else if (array[m1]<n)  a=m1;
     else /*(array[m1]>n)*/b=m1;
     m1=(a+b)>>1;
 }
 if (array[m1]<n) return m1;
 else /*(array[m1]>n)*/ return m1-1;
}

int main() {
 for(int n;cin>>n&&n;){
     int p=bin_search<uint>(primes,100000,n);
     if (primes[p]==n) cout<<0<<endl;
     else cout<<primes[p+1]-primes[p]<<endl;
 }
 return 0;
}