Sunday, October 24, 2010

Prime numbers

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/time.h>
#include <string.h>
#include <errno.h>

#define ERRNUM -1

typedef enum bool {
  FALSE =0,
  TRUE
} e_bool;

typedef enum stauts {
  FAILURE = 0,
  SUCCESS
} e_status;

typedef struct list* tsp_list;
struct list{
  unsigned int val;
  unsigned int index;
  tsp_list next;
};

e_status Append (unsigned int num, tsp_list *list)
{
  tsp_list lsp_primeNode = NULL;
  lsp_primeNode = (tsp_list) calloc (1, sizeof (struct list));
  if (NULL == lsp_primeNode)
  {
    fprintf (stderr, "ERROR: memory allocation failed.\n");
    return FAILURE;
  }
  lsp_primeNode->val = num;
  lsp_primeNode->next = NULL;

  if (NULL == *list)
  {
    *list = lsp_primeNode;
    lsp_primeNode->index = 1;
  }
  else
  {
    tsp_list node = *list;
    while (NULL != node->next)
    {
      node = node->next;
    }

    node->next = lsp_primeNode;
    lsp_primeNode->index = node->index + 1;
  }

  return SUCCESS;
}


e_bool IsPrime (unsigned int num, tsp_list list)
{
  if (1 >= num)
  {
    return FALSE;
  }

  switch (num)
  {
    case 2:
    case 3:
      return TRUE;
    default:
      {
        unsigned int lv_max_limit = (unsigned int) sqrt (num);
        
        while (list && list->val <= lv_max_limit)
        {
          if (0 == num % list->val)
          {
            return FALSE;
          }
          list = list->next;
        }
        return TRUE;
      }
  }
}

void GetPrimeList (tsp_list *list, unsigned count)
{
  unsigned int i = 2;
  unsigned int index = 1;
  struct timeval start;
  struct timeval end;
  struct timeval diff;

  if(-1 == gettimeofday(&start, NULL))
  {
    fprintf (stderr, "ERROR: %s\n", strerror (errno));
    return;
  }

  for (; i && 0 < count; i++)
  {
    if (TRUE == IsPrime (i, *list))
    {
      if(-1 == gettimeofday(&end, NULL))
      {
        fprintf (stderr, "ERROR: %s\n", strerror (errno));
        return;
      }

      /* Ref [http://www.linuxquestions.org/questions/programming-9/how-to-calculate-time-difference-in-milliseconds-in-c-c-711096] */
      diff.tv_sec =end.tv_sec - start.tv_sec ;
      diff.tv_usec=end.tv_usec - start.tv_usec;

      if(diff.tv_usec<0)
      {
        diff.tv_usec+=1000000;
        diff.tv_sec -=1;
      }

      printf ("%d (index: %d) (Time taken: %f sec)\n", i, index++, (float)(1000000LL*diff.tv_sec + diff.tv_usec)/1000000);
      
      if (FAILURE == Append (i, list))
      {
        return;
      }
      else
      {
        count --;
      }
    }
  }
}

int main (int argc, char *argv[])
{
  tsp_list primeList = NULL;
  int dig = 0;

  if ( 2 != argc)
  {
    return 0;
  }

  GetPrimeList (&primeList, (int) atoi(argv[1]));

  return 0;
}