Perfect Multiples

14Jun13

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.

Perfect Multiples

A perfect number is a number that is the sum of its divisors excluding itself (6 = 1 + 2 + 3 for example). The Least Common Multiple (or LCM) of a set of numbers is the smallest number that is divisible by all numbers in that set (24 is the LCM of 4, 6, 8 for example). Find the LCM of the first 4 perfect numbers.

Solution and answer (Perfect Multiples.c):

Includes: seal_bool, printDateAndTime.

/*
Solution and answer for problem "Perfect Multiples" (14th June 2013) of http://ContestCoding.WordPress.com/

Fri Jun 14 09:00:00 2013

The first four perfect numbers are: 6, 28, 496, and 8128.

The least common multiple of the first four perfect numbers is: 5291328.

Fri Jun 14 09:10:32 2013

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

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

bool f_IsPerfectNumber( const long p )
{
  long d = p / 2, s = 1;
  for( ; d > 1; d -- )
    if( p % d == 0 )
    {
      s += d;
      if( s > p )
        return false;
    }
  return s == p;
}

void main( void )
{
  short k = 0;
  long i = 2, pN[ 4 ];
  bool LCMFound;
  long LCM = 0;

  p_PrintDateAndTime();
  printf( "\n" );

  for( ; k < 4; i ++ )
    if( f_IsPerfectNumber( i ))
      pN[ k ++ ] = i;
  printf( "The first four perfect numbers are: " );
  for( k = 0; k < 4; k ++ )
  {
    printf( "%ld", pN[ k ] );
    if( k + 1 == 4 )
      printf( ".\n\n" );
    else
      if( k + 1 == 3 )
        printf( ", and " );
      else
        printf( ", " );
  }

  do
  {
    LCMFound = true;
    LCM += pN[ 3 ];
    for( k = 0; k < 3; k ++ )
      if( LCM % pN[ k ] != 0 )
      {
        LCMFound = false;
        break;
      }
  }
  while( !LCMFound );
  printf( "The least common multiple of the first four perfect numbers is: %ld.\n\n", LCM );

  p_PrintDateAndTime();
}
Advertisements


No Responses Yet to “Perfect Multiples”

  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: