Sunday 12 August 2012

Calculate a PRIME number LIST using C language


This C program calculates a list with first prime numbers.

Build the program


C is a compiled language, so we will need to install a C compiler: gcc
$ sudo aptitude install gcc

We copy this text in a file, e.g: prime_calculator.c

Next we compile the file:
$ gcc -o prime_calculator -lm prime_calculator.c -Wall

or if we want further optimization:
$ gcc -o prime_calculator -lm prime_calculator.c -Wall -O3

-lm option links the math library so we can calculate square roots.

Execute the program


After compilation, an executable appears: prime_calculator.
$ chmod a+x prime_calculator # we grant it execution permission.

If we want to show first ten prime numbers:
$ ./prime_calculator 10
PRIME LIST:
2 3 5 7 11 13 17 19 23 29

If we pass more than two arguments, it calculates the prime list but does not show anything. Just to measure its execution time:
$ time ./prime_calculator 10 *
real 0m0.008s
user 0m0.004s
sys 0m0.000s

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

typedef struct prime prime_t;

struct prime {
  unsigned long long number;
  prime_t *next;
};

void free_list(prime_t *p)
{
  prime_t *q;

  while(p!=NULL)
    {
      q = p->next;
      free(p);
      p = q;
    }
}

int main(int argn, char **argv)
{
  unsigned long long top, total, i, max;
  prime_t *first=NULL, *last, *p;
  short is_prime;

  if(argn<2)
    {
      fprintf(stderr, "Error: Wrong number of arguments: %d\n", argn);
      return -1;
    }

  /* Add number 2 to prime list. */
  p = malloc(sizeof(prime_t));
  if(p==NULL)
    {
      fprintf(stderr, "Error: Out of memory\n");
      return -1;
    }
  p->number=2;
  p->next = NULL;
  first = last = p;
  total = 1;

  top = atoll(argv[1]);
  i = 3;
  while(total<top)
    {
      p = first;
      is_prime = 1;
      max = floorl(sqrtl((long double)i));
      while(p != NULL && p->number <= max)
 {
   if(i % (p->number) != 0)
     {
       p = p->next;
     }
   else
     {
       /* i is not prime */
       is_prime = 0;
       break;
     }
 }

      if(is_prime)
 {
   /* i is a prime number. We add it to the list. */
   total += 1;
   p = malloc(sizeof(prime_t));
   if(p==NULL)
     {
       fprintf(stderr, "Error: Out of memory\n");
       free_list(first);
       return -1;
     }
   p->number = i;
   p->next = NULL;
   last->next = p;
   last = p;
 }

      i += 2;
    }
  
  if(argn == 2)
    {
      /* We print the prime list. */
      p = first;
      fprintf(stdout, "PRIME LIST: \n");
      while(p!=NULL)
 {
   fprintf(stdout, "%llu ", p->number);
   p = p->next;
 }
      fprintf(stdout, "\n");
    }

  /* Free prime list */
  free_list(first);

  return 0;
}


The program stores the prime list in a linked list.

To check if a number is prime it divides the number by already calculated primes. If none of them divides the number, we know it is another prime, and we add it to the list.

0 comentarios: