Div2 250 PrimeContainers

問題

入力 a₀ に対して a_k+1＝[a_k / 2] で数列を作る．その中で素数がいくつあるか求めよ．

考え方

そのまま，言われたとおりに演算をすればOK．素数判定は n に対して p²≦n の p までにしましょう．素数表作らなくても余裕で間に合う．

コード

class PrimeContainers
{
  bool isPrime(int n)
  {
    if( n < 2 ) return false;
    if( n == 2 ) return true;
    if( n % 2 == 0 ) return false;
    for( int k = 3 ; k * k <= n ; k += 2 ) {
      if( n % k == 0 ) return false;
    }
    return true;
  }
public:
  int containerSize(int N)
  {
    int ret = 0;
    for( int n = N ; n > 1 ; n >>= 1 ) {
      if( isPrime(n) ) ++ret;
    }
    return ret;
  }
};