C : Flying Reindeer Primes

03Dec12

I recently participated in the Advent Programming Contest organised by the IEEE Student Branch Klagenfurt (with support from Alpen-Adria-Universität Klagenfurt and Universität Passau), achieving a rank of 11th (out of 118 participants); as submissions of solutions to that contest are now closed, I’m posting here the solutions I submitted to that contest.

Problem (C; easy difficulty):

Flying Reindeer Primes

Santa needs to encrypt the communication channel to his reindeers. For the encryption he needs a set of consecutive prime numbers, one for each reindeer. The sleigh is pulled by nine reindeer.

Problem

Calculate the sum of 9 consecutive prime numbers larger or equal than a given integer number n. You program should read the starting number (maximum 200 000 000) from standard input and respond with the sum followed by a line break. The program should stop upon reading a negative number.

Sample Input

0
2
17
-1

Sample Output

100
100
287

Solution (C.c):

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

typedef struct t_CharStackNode_struct
{
  struct t_CharStackNode_struct *m_down;
  char m_char;
}
t_CharStackNode;

typedef enum
{
  false = 0,
  true
}
bool;

static t_CharStackNode *g_charStack_top = NULL;
static int g_charStack_int = 0;
static bool g_charStack_errorOccurredConvertingContentToInt = true;

void p_CharStack_Reset( void );
void p_CharStack_Input( FILE *p );
bool f_CharStack_Empty( void );
void p_CharStack_ConvertContentToInt( void );
bool f_CharStack_ErrorOccurredConvertingContentToInt( void );
int f_CharStack_Int( void );

bool f_IsPrime( int p );

int main( void )
{
  int i;
  l_LOOP:
    p_CharStack_Input( stdin );
    p_CharStack_ConvertContentToInt();
    if( f_CharStack_ErrorOccurredConvertingContentToInt())
      return -1;
    i = f_CharStack_Int();
    if(( i >= 0 ) && ( i <= 200000000 ))
    {
      int numberOfPrimes = 0, totalOfPrimes = 0;
      for( ; numberOfPrimes < 9; i ++ )
        if( f_IsPrime( i ))
        {
          numberOfPrimes ++;
          totalOfPrimes += i;
        }
      printf( "%d\n", totalOfPrimes );
      goto l_LOOP;
    }
    else
      if( i >= 0 )
        return -2;
  return 0;
}

static void p_CharStack_Delete( t_CharStackNode *p )
{
  if( p != NULL )
  {
    p_CharStack_Delete( p->m_down );
    free( p );
  }
}

void p_CharStack_Reset( void )
{
  p_CharStack_Delete( g_charStack_top );
  g_charStack_top = NULL;
  g_charStack_int = 0;
  g_charStack_errorOccurredConvertingContentToInt = true;
}

void p_CharStack_Input( FILE *p )
{
  char c;
  t_CharStackNode *n;
  p_CharStack_Reset();
  do
  {
    fscanf( p, "%c", &c );
    if( c != '\n' )
    {
      n = ( t_CharStackNode* )malloc( sizeof( t_CharStackNode ));
      n->m_down = g_charStack_top;
      g_charStack_top = n;
      n->m_char = c;
    }
  }
  while( c != '\n' );
}

bool f_CharStack_Empty( void )
{
  return ( g_charStack_top == NULL );
}

void p_CharStack_ConvertContentToInt( void )
{
  if( f_CharStack_Empty())
    g_charStack_errorOccurredConvertingContentToInt = true;
  else
  {
    t_CharStackNode *n = g_charStack_top;
    int multiplier = 1;
    g_charStack_int = 0;
    g_charStack_errorOccurredConvertingContentToInt = false;
    do
    {
      if(( n->m_char >= '0' ) && ( n->m_char <= '9' ))
      {
        g_charStack_int += (( n->m_char - '0' ) * multiplier );
        n = n->m_down;
        multiplier *= 10;
      }
      else
        if(( n->m_char == '-' ) && ( n->m_down == NULL ))
        {
          g_charStack_int = -g_charStack_int;
          n = n->m_down;
        }
        else
          g_charStack_errorOccurredConvertingContentToInt = true;
    }
    while(( n != NULL ) && ( !g_charStack_errorOccurredConvertingContentToInt ));
  }
}

bool f_CharStack_ErrorOccurredConvertingContentToInt( void )
{
  return g_charStack_errorOccurredConvertingContentToInt;
}

int f_CharStack_Int( void )
{
  return g_charStack_int;
}

bool f_IsPrime( int p )
{
  if( p < 2 )
    return false;
  if( p == 2 )
    return true;
  if(( p % 2 ) == 0 )
    return false;
  int i = 3, i_squared;
  l_LOOP:
    if( i == p )
      return true;
    i_squared = i * i;
    if( i_squared > p )
      return true;
    if( i_squared == p )
      return false;
    if(( p % i ) == 0 )
      return false;
    i ++;
    goto l_LOOP;
}

Testing:

gcc -std=c99 -Wall -lm C.c
mv a.out C
./C
0
100
2
100
17
287
-1
Advertisements


No Responses Yet to “C : Flying Reindeer Primes”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: