Consecutive Prime Digits

05Jul13

In the twelve months from March 2013 to March 2014, I programmed solutions to the problems posted on the Contest Coding blog run by Lewis Cornwall, solving 33 problems (out of 47) and achieving a position of 4th on the leaderboard (out of 23).

As that blog has now been discontinued, I’m posting here the solutions I programmed to those problems.

Consecutive Prime Digits

A prime number is a number with only two factors, itself and one (31 for example). Take the digits of the first 100 prime numbers and write them down in order:

2 3 5 7 1 1 1 3 1 7 etc.

Find the largest sum of 5 consecutive digits in this series.

Solution and answer (Consecutive Prime Digits.c):

Includes: printDateAndTime, seal_intToString, seal_stringConcatenation, seal_bool.

/*
Solution and answer for problem "Consecutive Prime Digits" (5th July 2013) of http://ContestCoding.WordPress.com/

Fri Jul 05 09:00:00 2013

37

Fri Jul 05 09:00:01 2013

Solution programmed in C using Leonardo IDE 3.4.1; solution took ~1s to run on a 80MHz PowerPC 601.
*/

#include "printDateAndTime.h"
#include "seal_intToString.h"
#include "seal_stringConcatenation_C.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

void p_PrimeNumbers_Reset( void );
void p_PrimeNumbers_Generate( const short p /* Number of prime numbers to generate. */ );
long f_PrimeNumber( void );

static char *digits = NULL;

void p_Exit( void )
{
  p_PrimeNumbers_Reset();
  if( digits != NULL )
    free( digits );
}

void main( void )
{
  long i;
  size_t k = 0;
  short largest_sum = 0;

  p_PrintDateAndTime();

  atexit( p_Exit );
  p_PrimeNumbers_Generate( 100 );
  i = f_PrimeNumber();
  while( i != -1 )
  {
    if( digits == NULL )
      digits = f_seal_IntToString( i, false );
    else
    {
      char *s = f_seal_IntToString( i, false );
      char *cS = f_seal_ConcatenateStrings_C( digits, s, NULL );
      free( s );
      free( digits );
      digits = cS;
    }
    i = f_PrimeNumber();
  }
  for( ; k < strlen( digits ); k ++ )
    digits[ k ] = digits[ k ] - '0';
  for( k = 0; k < strlen( digits ) - 4; k ++ )
  {
    short sum = digits[ k ] + digits[ k + 1 ] + digits[ k + 2 ] + digits[ k + 3 ] + digits[ k + 4 ];
    if( sum > largest_sum )
      largest_sum = sum;
  }
  printf( "\n%d\n\n", largest_sum );

  p_PrintDateAndTime();

  exit( EXIT_SUCCESS );
}

typedef struct t_PrimeNumber_struct
{
  struct t_PrimeNumber_struct *m_n;
  long m_pN;
}
t_PrimeNumber;

static void p_PrimeNumbers_Delete__private( t_PrimeNumber *p )
{
  if( p != NULL )
  {
    p_PrimeNumbers_Delete__private( p->m_n );
    free( p );
  }
}

static t_PrimeNumber *g_first = NULL, *g_last = NULL, *g_current = NULL;

void p_PrimeNumbers_Reset( void )
{
  p_PrimeNumbers_Delete__private( g_first );
  g_first = NULL;
  g_last = NULL;
  g_current = NULL;
}

static t_PrimeNumber *f_PrimeNumbers_New__private( const long p )
{
  t_PrimeNumber *n = ( t_PrimeNumber* )malloc( sizeof( t_PrimeNumber ));
  n->m_n = NULL;
  n->m_pN = p;
  return n;
}

static bool f_PrimeNumbers_DivisibleByExistingPrimeNumber__private( const long p )
{
  t_PrimeNumber *n = g_first;
  while( n != NULL )
  {
    if( p % n->m_pN == 0 )
      return true;
    n = n->m_n;
  }
  return false;
}

void p_PrimeNumbers_Generate( const short p /* Number of prime numbers to generate. */ )
{
  short i = 0;
  long k = ((( g_last == NULL ) || ( g_last->m_pN == 2 ))?3:g_last->m_pN + 2 ), old_k = k;
  if( p <= 0 )
    return;
  if( g_first == NULL )
  {
    g_first = f_PrimeNumbers_New__private( 2 );
    g_last = g_first;
    g_current = g_first;
    i ++;
  }
  for( ; i < p; k += 2 )
  {
    if( k < old_k )
    {
      fprintf( stderr, "p_PrimeNumbers_Generate - k overflowed.\n" );
      exit( EXIT_FAILURE );
    }
    old_k = k;
    if( !f_PrimeNumbers_DivisibleByExistingPrimeNumber__private( k ))
    {
      g_last->m_n = f_PrimeNumbers_New__private( k );
      g_last = g_last->m_n;
      if( g_current == NULL )
        g_current = g_last;
      i ++;
    }
  }
}

long f_PrimeNumber( void )
{
  const long pN = (( g_current == NULL )?-1:g_current->m_pN );
  if( g_current != NULL )
    g_current = g_current->m_n;
  return pN;
}
Advertisements


No Responses Yet to “Consecutive Prime Digits”

  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: