別バージョン。bsoearchを使ってみた。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 1000
int cmp_int(const void *a, const void *b){ return *(int*)a - *(int*)b;}
int main()
{
  static int buf[N];
  int i,j,*p, key, save;
  for(i = 2; i < sqrt(N); ++i)
  {
    if( buf[i] ) continue;
    for(j = i+i; j < N; j += i) buf[j] = 1;
  }
  for(i = 2, j = 0; i < N; ++i)
    if( !buf[i] ) buf[j++] = i;
  buf[j] = 0; save = N;
  for(i = 0; buf[i] < save; ++i)
  {
    key = N - buf[i];
    if(NULL != (p = bsearch(&key,buf, j, sizeof(int), cmp_int)))
    {
      printf("%d %d\n", buf[i], *p);
      save = *p;
    }
  }
  return 0;
}