【AOJ 1276】Prime Gap

問題

Prime Gap | Aizu Online Judge

ソースコード

#include <iostream>
#include <cstring>

#define rep(i,n) for(int i = 0 ; i < n ; i++)
#define MAX_N 1299710

using namespace std;

int main(){
  int n;
  bool prime[MAX_N];

  memset(prime,true,sizeof(prime));

  for(int i = 2; i*i < MAX_N ; i++){
    if(prime[i]){
      for(int j = i*2 ; j <= MAX_N ; j+=i){
        prime[j] = false;
      }
    }
  }

  while(cin >> n, n){
    if(prime[n]){
      cout << 0 << '\n';
    }else{
      int l,r;
      l=r=1;
      while(!prime[n-l]) l++;
      while(!prime[n+r]) r++;
      cout << l+r << '\n';
    }
  }
}