Round 2 : Prime Decomposition

06Sep13

I recently participated in the Contest Coding Cup 2013 organised by Lewis Cornwall, being amongst the six (out of fourteen) participants to progress to the final round, in which I achieved a rank of 6th.

As submissions of solutions to that contest are now closed, I’m posting here the solutions I submitted to that contest.

Problem (Round 2):

Prime Decomposition

A prime number is a number with only two factors, itself and one (17 for example). The prime decomposition of a number is a list of prime numbers that when multiplied together are equal to that number. Find the prime decomposition of 3300.

Solution (Prime_Decomposition.java):

/*
Solution and answer for problem "Prime Decomposition (Contest Coding Cup - Round 2)" (6th September 2013) of http://contestcoding.wordpress.com/

Wed Nov 06 10:10:19 GMT+00:00 2013

2 x 2 x 3 x 5 x 5 x 11

Wed Nov 06 10:10:20 GMT+00:00 2013

Solution programmed in Java using Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition); solution took ~1s to run on an 80MHz PowerPC 601.
*/

import java.util.Date;

public class Prime_Decomposition
{
  private static final int N = 3300;

  public static void main( String p[] )
  {
    System.out.println( new Date() + "\n" );

    // Determine the prime numbers in the range of numbers 0..N
    boolean b[] = new boolean[ N + 1 ];
    for( int i = 0; i < b.length; i ++ )
      b[ i ] = true;
    b[ 0 ] = false;
    b[ 1 ] = false;
    int number_of_primes = 0;
    for( int i = 2; i < b.length; i ++ )
      if( b[ i ] )
      {
        number_of_primes ++;
        for( int k = i + i; k < b.length; k += i )
          b[ k ] = false;
      }

    // Make an array of the prime numbers in the range 0..N
    int primes[] = new int[ number_of_primes ];
    for( int i = 0, k = 0; i < b.length; i ++ )
      if( b[ i ] )
        primes[ k ++ ] = i;

    for( int i = primes.length - 1; i >= 0; i -- )
      if( determinePrimeDecomposition( i, primes[ i ], primes ))
      {
        System.out.println( " x " + primes[ i ] );
        break;
      }

    System.out.println( "\n" + new Date());
  }

  private static boolean determinePrimeDecomposition( int p_index, int p_product, int p_primes[] )
  {
    for( int i = p_index; i >= 0; i -- )
    {
      int p = p_product * p_primes[ i ];
      if( p == N )
      {
        System.out.print( p_primes[ i ] );
        return true;
      }
      else
        if( p < N )
          if( determinePrimeDecomposition( p_index, p, p_primes ))
          {
            System.out.print( " x " + p_primes[ i ] );
            return true;
          }
    }
    return false;
  }
}

Result:

Wed Nov 06 10:10:19 GMT+00:00 2013

2 x 2 x 3 x 5 x 5 x 11

Wed Nov 06 10:10:20 GMT+00:00 2013
Advertisements


No Responses Yet to “Round 2 : Prime Decomposition”

  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: