Palindromic Primes

22Mar13

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.

Palindromic Primes

A palindromic number is a number that reads the same backwards as forwards (1991 for example). A prime number is a number with only two factors, itself and one (17 for example). A palindromic prime number is a number that is both a palindromic number and a prime number (151 for example). Find the largest 5-digit palindromic prime number.

Solution and answer (Palindromic Primes.c):

Includes: seal_bool, printDateAndTime.

/*
Solution and answer for problem "Palindromic Primes" (22nd March 2013) of http://ContestCoding.WordPress.com/

Fri Mar 22 09:00:00 2013

98689 is the largest 5-digit palindromic prime.

Fri Mar 22 09:00:14 2013

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

#include "seal_bool.h"
#include "printDateAndTime.h"
#include <stdio.h>

bool f_IsPalindrome( long p )
{
  long reversed_p = 0;
  const long original_p = p;
  while( p != 0 )
  {
    reversed_p *= 10;
    reversed_p += ( p % 10 );
    p /= 10;
  }
  return reversed_p == original_p;
}

#define k_MAXIMUM_PRIME /* + 1 */ 100000

void main( void )
{
  p_PrintDateAndTime();
  printf( "\n" );
  {
    bool prime[ k_MAXIMUM_PRIME ];
    long i = 3, k, largest_prime;
    for( ; i < k_MAXIMUM_PRIME; i += 2 )
      prime[ i ] = true;
    for( i = 3; i < k_MAXIMUM_PRIME; i += 2 )
      if( prime[ i ] )
      {
        for( k = i + i; k < k_MAXIMUM_PRIME; k += i )
          prime[ k ] = false;
        largest_prime = i;
      }
    for( i = largest_prime; ; i -= 2 )
      if( prime[ i ] )
        if( f_IsPalindrome( i ))
        {
          printf( "%ld is the largest 5-digit palindromic prime.\n", i );
          break;
        }
  }
  printf( "\n" );
  p_PrintDateAndTime();
}
Advertisements


No Responses Yet to “Palindromic 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: