#include<iostream>
#include<cmath>
using namespace std;
int map[100000];
int isPrime(int n){
    if(n==0||n==1)return 0;
    if(n==2)return 1;
    for(int i=2;i<=sqrt(n*1.0);i++){
        if(n%i==0)return 0;
    }
    return 1;
    
}
void cal(){
    int count=0;
    for(int i=2;i<=1299709;i++){
        if(isPrime(i)){
            map[count]=i;
            count++;
        }
    }
}
int find_m(int m){
    for(int i=0;i<100000;i++){
        if(m==map[i])return 1;
    }
    return 0;
}
int find(int n){
    int k;
    for(int i=0;i<100000;i++){
        if(map[i]>n){
            k=i;
            break;
        }
    }
    return k;
}
int main (){
    int n;
    cal();
    cin>>n;
    while(n!=0){
        if(find_m(n)==1)cout<<0<<endl;
        else{
            int temp=find(n);
            cout<<map[temp]-map[temp-1]<<endl;
        }
        cin>>n;
    }
   // system("pause");
    return 0;
}

• Re:打表~1610MS水过，大牛指点，时间也忒久了~ (46) maxh123ok1 2011-08-17 22:08:59