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

int *primes, tblSize = 10, idx = 0, n = 2, maxFrom, maxStep, maxLength = 0;

void makePrimes();

void makePrimes()
{
  int i, j;
  for (i = primes[idx - 1] + 2; i < INT_MAX / 10; i += 2) {
    for ( j = 0; (i % primes[j]) && (i > primes[j]*primes[j]); ++j);
    if (i % primes[j])
      primes[idx++] = i;
    if (idx == tblSize) {
      tblSize *= 2;
      primes = (int *)realloc(primes, sizeof(int) * tblSize);
      if (primes == NULL) {
        printf("prime table size expanded error\n");
        exit(0);
      } else {
        printf("prime table size expanded to %d\n", tblSize);
      }
    }
  }
}

int seqLen(int i, int j)
{
  int len = 2;
  int step = primes[j] - primes[i];
  int n = primes[j] + step;
  while (1) {
    while (n > primes[j])j++;
    if (n == primes[j]) {
      len++;
      n += step;
    } else break;
  }
  return len;
}

int main(void)
{
  int i, j, t;
  primes = (int *)malloc(sizeof(int) * tblSize);
  primes[idx++] = 2;
  primes[idx++] = 3;
  makePrimes();
  printf("number of primes = %d\n", idx);
  printf("calculating...\n");
  for ( i = 0; i < idx; ++i) {
    for ( j = i + 1; j  < idx; ++j  ) {
      t = seqLen(i, j);
      // printf("i j = %d %d %d\n", i,j,t);
      if (maxLength < t) {
        maxFrom = primes[i];
        maxStep = primes[j] - primes[i];
        maxLength = t;
        printf("from step length = %d %d %d\n", maxFrom, maxStep, maxLength);
      }
    }
  }
  // printf("from step length = %d %d %d\n", maxFrom, maxStep, maxLength);

  return 0;
}