TopCoder SRM291 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について、おおまかに説明する。

素数というのは、1よち大きい整数で、1とそれ以外で割り切れないものである。もしあるNに対してN-10からN+10にある数で割り切れない場合、その数Nは「素数から遠い」と考えられる。つまりN-10からN+10までの数はすべて素数でないということである。さて、AとBという二つの整数が与えられる。このとき、AとBの間にある「素数から遠い」数はいくつあるかを求めて返せ。なお、常にB>=Aの関係が成り立つものとする。

私の解答はこちら。

public class FarFromPrimes {

 public int count(int A, int B) {
  int nFarFromPrime = 0;
  for( int i=A ; i<=B ; i++ ){
   boolean isFarFromPrime = true;
   for( int j=i-10 ; j<=i+10 ; j++ ){
    boolean isOK = false;
    for( int k=2 ; k<=j/2 ; k++ ){
     if( j % k == 0 ){ // 途中で素数でないと分かればOK
      isOK = true;
      break;
     }
    }
    if( isOK == false ){ // 素数でない数がi-10からi+10の間に存在した
     isFarFromPrime = false;
     break;
    }
   }
   if( isFarFromPrime == true ) nFarFromPrime++; // 全部素数ならカウント
  }
  return nFarFromPrime;
 }

}

得点は183.67/250、中央値は約190点。ある数nが素数か否かの検討は本来ならsqrt(n)まで調べればよいはずなのですが、面倒なので、n/2まで調べる方針で対応しました。