#include <stdio.h>
#include <stdlib.h>

/* 数の上限 */
#define MAX_NUM (int)(1e9)

/* 素数リストの要素数の上限 */
#define MAX_PRIME (int)(1e8)

/* 関数のプロトタイプ宣言 */
void fill_list(long long int, int*);
void make_primelist(int*);

/* 素因数が偶数かどうかを記憶する配列 */
char *is_even;

int main(){

  int even=0; /* 素因数の数が偶数であるものの数 */
  int i;
  
  /* 素数リストを作成 */
  int *primelist;
  primelist = (int*)calloc(MAX_PRIME, sizeof(int));
  make_primelist(primelist);

  /* 素因数の数か偶数かどうかのリストを作成 */
  is_even = (char*)calloc(MAX_NUM, sizeof(char));
  is_even[1] = 1;
  fill_list(1, primelist);

  for(i=2; i<MAX_NUM; i++){
    /* 素因数の数を数え，偶数ならカウント */
    even += is_even[i];;

    /* 素因数の数が偶数であるものが50%以上になったら終了する */
    /* 2から数え始めているので，母数はi-1個 */
    if( even*2 >= (i-1)){
      printf("\rNG in %d\n", i);
      return 0;
    }

    /* 途中経過を表示 */
    if(i % (10000000) == 0){
      printf("\r%d : OK", i);
      fflush(stdout);
    }
  }

  printf ("\nOK!\n");

  /* メモリの開放 */
  free(primelist);
  free(is_even);

  return 0;
}

/* 素因数の数が偶数かどうかのリストを作る */
/* 素数から合成数を作っていくことでリストを埋める */
/* この関数では，nにprimelist内の素数を1個以上かけて作られる数について埋める */
void fill_list(long long int n, int* primelist){
  /* 素数リストに数がない場合 */
  if(primelist[0] == 0) return;

  int i;
  long long int x;
  for(i=0; primelist[i] != 0; i++){
    /* nにprimelist内の素数1個をかける */
    x = n*primelist[i];

    /* 数が上限を超えたらそれ以上大きな素数については考えない */
    if(x >= MAX_NUM) break;

    /* この数の素因数の数はnの素因数の数+1となる */
    is_even[x] = !is_even[n];

    /* この数に，かけた素数以上の素数をかけて作られる数についてリストを埋める */
    fill_list(x, primelist+i);
  }
}

/* 素数リストを作成する関数 */
/* エラトステネスの篩を用いて素数リストを作成 */
void make_primelist(int* primelist){
  int i,j;
  int n=0;  /* 素数の数 */
  char *flag; /* 素数かどうかを表すフラグ */
  flag = (char*)calloc(MAX_NUM, sizeof(char));

  /* Nまで篩うためにはsqrt(N)までの素数で篩えばよい */
  for(i=2; i*i<MAX_NUM; i++){
    if(flag[i] == 1) continue;
    /* 素数が見つかった場合，その倍数を素数候補から除外 */
    for(j=i*i; j<MAX_NUM; j+=i){
      flag[j] = 1;
    }
    /* 見つかった素数を素数リストに追加 */
    primelist[n++] = i;
  }

  /* sqrt(N)以上の数は倍数を除外する必要がない */
  for(; i<MAX_NUM; i++){
    if(flag[i] == 0) primelist[n++] = i;
  }
  free(flag);
}