Round 3 250 - SieveOfEratosthenes

TCO

問題

wikipedia:エラトステネスの篩を行うときに，最後に省かれる合成数は何？

考え方

合成数 n は n＝pq (p＜q) と書ける．篩の過程では p(が素数として)での篩の時に消えるので，考えるべきは最小素因数．また，最小素因数 p が同じになる n＝pq と m＝pr (q＜r) については m の方が後に省かれる．
なので求めるべきは最小素因数が最大になる数で，そのなかでも最大の数．実質的に n＝pq のとき q も素数であればいい…と言いたいが，例外がある．
2 素数 p＜q のもとで pq＜p3≦n＜q2となる場合には p3 を出力する必要がある．で，その条件を満たすのは n＝8 の場合だけなので例外処理でも書けばOK．

コード

とりあえず偶数処理だけ別にして（しなくても間に合うっぽいけど）高速にしたコード．

#include <vector>
#include <cmath>
using namespace std;

class SieveOfEratosthenes
{
  vector<bool> prime;
  void init(int maxNum)
  {
    int sq = (int)sqrt((double)maxNum);
    int ssq = (int)sqrt((double)sq);
    prime.resize(sq/2+10, true);
    prime[0] = false; // == 1
    for( int i = 1 ; i <= ssq ; ++i ) {
      int p = 2 * i + 1;
      for( int j = p * p / 2 ; j < prime.size() ; j += p )
        prime[j] = false;
    }
  }
  bool isPrime(int n)
  {
    int sq = (int)sqrt((double)n) / 2;
    for( int i = 1 ; i <= sq ; ++i )
      if( prime[i] && n % (2 * i + 1) == 0 )
        return false;
    return true;
  }
public:
  int lastScratch(int maxNum)
  {
    init(maxNum);
    switch(maxNum) 
    {
    case 4: case 5: return 4;
    case 6: case 7: return 6;
    case 8: return 8;
    default:
      int p = (int)sqrt((double)maxNum), q;
      if( p % 2 == 0 ) --p;
      for( p /= 2 ; p > 0 ; --p ) if( prime[p] ) break;
      p = 2 * p + 1;
      q = maxNum / p;
      if( q % 2 == 0 ) --q;
      for( ; q > p ; q -= 2 ) if( isPrime(q) ) break;
      return (p * q);
    }
  }
};