# prime.awk    (Nim-premiers)
# Nombres premiers <= maxi et fonction de Grundy
#
# J-P Davalan 15/04/2003
# http://nim.site.voila.fr/prime/index.html
#
# usage :
#          echo ""|gawk -v maxi=150 -f prime.awk

END {
  if(maxi=="") maxi = 150;
  prime[0]=2;prime[1]=3;prime[2]=5;
  n=2;
  test=1;
  for(i=7; i<=maxi;i = i+2) {
    test=1;
    a = 1+int(sqrt(i));
    for(j=0;test && j<=n  && prime[j]<= a; j++) {
      if(i % prime[j] == 0) test=0;
    }
    if(test) {
      n += 1;
      prime[n]=i;
    }
  }
  print ""
  gr[0]=0;gr[1]=1;
  for(i=2; i< prime[n]; i++) {
    delete tab;
    for(j=0; prime[j] <= i; j++) {
      tab[gr[i-prime[j]]] = 1;
    }
    for(j=0;tab[j]==1;j++) ;
    gr[i]=j;
  }
  printf("var primes = new Array(2");
  for(i=1;i<=n;i++) {
    printf(",%d",prime[i]);
  }
  print ");"
  printf("var gr = new Array(0");
  for(i=1;i<=prime[n];i++) {
    printf(",%d",gr[i]);
  }
  print ");"
}