読者です 読者をやめる 読者になる 読者になる

UVa11105 Semi-prime H-numbers

問題
http://uva.onlinejudge.org/external/111/11105.html

概要
4n+1で表される数を H-number と呼ぶ。H-number は 3 種類に分けられる。1と、H-primeと、H-composite である。1以外の H-number の積で表されない H-number を H-prime と呼び、それ以外の 1でない H-number を H-composite と呼ぶ。
また、さらに 1以外の 2つの H-prime の積として表される H-number を H-semiprime と呼ぶ。入力された数以下の H-semiprime の数を答えよ。

制約
入力の H-prime <= 1,000,001

解法
エラトステネスの篩のように H-prime を列挙したあと、2つの H-prime の積で表される H-semiprime を決める。

const int MAX = 1000001;
const int MAX_4 = 250000;
 
bool is_hprime[MAX+10], is_hsemiprime[MAX+10];
int hPrime[MAX_4+1], Psize;
int hSemiPrime[MAX_4+1], SemiPsize;
 
void makeHPrime() {
   
  fill(is_hprime, is_hprime+MAX, true);
  for(int i=0; i<5; i++) is_hprime[i] = false;
  for(int i=5; i<=MAX; i+=4) {
    if(is_hprime[i]) {
      if(Psize>MAX_4) break;
      hPrime[Psize++] = i;
      for(ll j=2*i; j<=MAX; j+=i) {
        is_hprime[j] = false;
      }
    }
  }
   
}
 
 
void makeHSemiPrime() {
   
  for(int i=0; i<Psize; i++) {
    for(int j=0; j<Psize; j++) {
      if(hPrime[i]*hPrime[j] > MAX) break;
      if(is_hsemiprime[hPrime[i]]) continue;
      if(is_hsemiprime[hPrime[j]]) continue;
      if(is_hsemiprime[hPrime[i]*hPrime[j]]) continue;
      is_hsemiprime[hPrime[i]*hPrime[j]] = true;
      hSemiPrime[SemiPsize++] = hPrime[i]*hPrime[j];
    }
  }
   
  sort(hSemiPrime, hSemiPrime+SemiPsize);
   
}
 
int main() {
   
  makeHPrime();
  makeHSemiPrime();
   
  int H;
  while(cin >> H && H) {
    cout << H << ' ';
     
    int cnt;
    for(cnt=0; cnt<SemiPsize && hSemiPrime[cnt] <= H; cnt++);
    cout << cnt << endl;
  }
   
  return 0;
}