// a small, _bad_ program that creates n random numbers, determines which are 
// prime, prints out all the prime ones, with the largest one last

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// return a heap-allocated array of random integers of size arrlen in the range
// [2,maxnum]
int * make_random_array(int arrlen, int maxnum) {
  int * ans = (int*)malloc(arrlen*sizeof(int));
  int i = 0;
  srandom(time(NULL));
  for(; i < arrlen; ++i)
    ans[i] = (random() % (maxnum - 2)) + 2;
  return ans;
}

int is_prime(int x) {
  int y=2;
  for(; y < x; ++y)
    if((x % y) == 0)
      return 0;
  return 1;
}

int * find_primes(int arrlen, int * arr) {
  int * ans = (int*)calloc(arrlen,sizeof(int));
  int i=0;
  for(; i < arrlen; ++i)
    if(is_prime(arr[i]))
      ans[i] = 1;
  return ans;
}

// return -1 if there are no primes
int find_largest(int arrlen, int * nums, int * is_primes) {
  // "clever" recursive algorithm
  if(arrlen==0)
    return -1;
  if(!is_primes[arrlen-1])
    return find_largest(arrlen-1,nums,is_primes);
  if(find_largest(arrlen-1,nums,is_primes) > nums[arrlen-1])
    return find_largest(arrlen-1,nums,is_primes);
  return nums[arrlen-1];
}

void print_output(int arrlen, int * nums, int * is_primes, int largest) {
  fprintf(stdout,"\nPrimes except largest: ");
  int i=0;
  for(; i < arrlen; ++i)
    if(is_primes[i] && nums[i] != largest)
      printf("%d ",nums[i]);
  if(largest != -1)
    fprintf(stdout,"\nLargest prime: %d\n",largest);
}

int main(int argc, char**argv) {
  if(argc != 3) {
    fprintf(stderr,"usage: %s number-of-tries maximum-number\n",argv[0]);
    return 1;
  }
  int arrlen = atoi(argv[1]);
  int maxnum = atoi(argv[2]);
  if(arrlen <= 0 || maxnum <= 0) {
    fprintf(stderr,"usage: %s requires two positive numbers\n",argv[0]);
    return 1;
  }
  int * random_array = make_random_array(arrlen,maxnum);
  int * primes       = find_primes(arrlen,random_array);
  int   largest      = find_largest(arrlen,random_array,primes);
  print_output(arrlen,random_array,primes,largest);
  return 0;
}