2013年7月31日水曜日

TopCoder SRM471 Div2 250Pts

このTopCoderの問題は検索にかけても現れないのですが、簡単に説明してみます。

エリーは"2で割る"問題が大好きである。これにより彼女は2で割らなければならない問題を意味している。エリーはそれ自身が素数を含む数があることに気づいた。数XがYという数字を持つというのは、Y=X/2^k(非負の整数kで割って、切り捨てられたもの)を満たしているときをいう。エリーはすべての正の整数を"prime container"と呼び、その数が含む素数の数をprime containerの大きさと定義した。例えば、7の大きさは2である。これは7/1=7、7/2=3がともに素数だからである(訳注:これを続けると7/2^2=1なので素数にならない)。同様に47は5、959は6が得られる。正の整数Nが与えられたとき、その数のprime containerの大きさを求めることでエレノラを手伝え。

私の解答はこちら。

public class PrimeContainers {

 public int containerSize(int N) {
  int ans = 0;
  for( int i=1 ; i<=N ; i=i*2 ){
   int target = N / i;
   if( isPrime(target) && target >= 2 ){
    ans++;
   }
  }
  return ans;
 }

 boolean isPrime(int n){ // 素数か判定するプログラム
  int end = (int)Math.sqrt(n);
  for( int i=2 ; i<=end ; i++ ){
   if( n % i == 0 ) return false;
  }
  return true;
 }
}

得点は218.65/250、1回のsubmitでシステムテストクリア。後半の英文の意味が拾いにくかったので、意訳してしまいました。

0 件のコメント:

コメントを投稿

フォロワー

ページビューの合計