ちょっと気になった。差し替え。
#include <stdlib.h>
int prime(int n){
  int i, notprime, ret, *is_prime = (int*)malloc(sizeof(int) * (n + 1));
  for (i = 2; i <= n; i++) is_prime[i] = 1;
  is_prime[0] = is_prime[1] = 0;
  for (i = 2; i <= n; i++) {
    notprime = i;
    while ((notprime += i) <= n) is_prime[notprime] = 0;
  }
  ret = is_prime[n];
  free(is_prime);
  return ret;
}