#define MAX_NUM 1000

/* 関数のプロトタイプ宣言 */
int is_prime(int);
int is_sum_of_power2_and_prime(int);

int main(){
  int i,k;
  for(i=3; i<MAX_NUM; i+=2){
    /* 奇数iが2の累乗と素数の和で表せるか確認 */
    if(k=is_sum_of_power2_and_prime(i)){
      printf("%d = 2^%d + %d\n", i, k, i - (1<<k) );
    }
    else printf("NG in %d\n", i);
  }
  return 0;
}

/* nが素数かどうかを判定する関数 */
/* 素数なら1，そうでないなら0を返す */
int is_prime(int n){
  /* 1は素数ではない */
  if(n < 2) return 0;

  /* sqrt(n)までのすべてのiで割りきれなければ素数 */
  int i;
  for(i=2; i*i<=n; i++){
    if(n%i==0) return 0;
  }
  return 1;
}

/* nが2の累乗と素数の和で表せるかどうかを返す関数 */
/* 表せるなら２の指数を，そうでないなら0を返す */
int is_sum_of_power2_and_prime(int n){
  int i;
  for(i=0; (1<<i) < n; i++){
    /* n - 2^i が素数となればよい */
    /* 1<<i = 2^i を利用 */
    if( is_prime( n - (1<<i) ) ){
      return i;
    }
  }
  return 0;
}