Mersenne Prime

29Sep13

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.

Mersenne Prime

A prime number is a number with only two factors, itself and one (17 for example). A Mersenne number is a number which when added to one is a power of two (31 = 25 – 1 for example). The base of a Mersenne number is the number which when two is taken to the power of that number equates to the Mersenne number add one (5 is the base of the Mersenne number 31 for example). Find the smallest Mersenne number such that the base of that Mersenne number is a prime number, but the Mersenne number itself is not.

Solution and answer (Mersenne_Prime.java):

/*
Solution and answer for problem "Mersenne Prime" (29th September 2013) of http://ContestCoding.WordPress.com/

Sun Sep 29 09:00:00 GMT+01:00 2013

2047

Sun Sep 29 09:00:00 GMT+01:00 2013

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

import java.util.Date;

public class Mersenne_Prime
{
  public static void main( String p[] )
  {
    System.out.println( new Date());

    int base = -1, M;
    boolean primes[] = null;
    do
    {
      M = ( int )Math.pow( 2, ++ base ) - 1;
      if( primes == null || Math.max( base, M ) >= primes.length )
        primes = calculatePrimes( Math.max( base, M ));
    }
    while( !( primes[ base ] && !primes[ M ] ));
    System.out.println( "\n" + M + "\n" );

    System.out.println( new Date());
  }

  private static boolean[] calculatePrimes( int p )
  {
    boolean b[] = new boolean[ Math.max( p + 1, 3 ) ];
    for( int i = 0; i < b.length; i ++ )
      b[ i ] = true;
    b[ 0 ] = false;
    b[ 1 ] = false;
    for( int i = 2; i < b.length; i ++ )
      if( b[ i ] )
        for( int k = i + i; k < b.length; k += i )
          b[ k ] = false;
    return b;
  }
}
Advertisements


No Responses Yet to “Mersenne Prime”

  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: