#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; }
Sunday, October 24, 2010
Prime numbers
Labels:
C
,
number
,
prime
,
Programming
,
time
,
time interval
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment