E : Please improve my program

05Dec13

I recently participated in the Advent Programming Contest 2013 organised by the IEEE Student Branch Klagenfurt (with support from Alpen-Adria-Universität Klagenfurt), wherein – as I’d recently received from Udacity a certificate for Introduction to Programming : Problem Solving with Java (CS046) – I challenged myself to program my solutions to the problems posed by the contest using only Java (I’d used C and C++ when I’d participated in the contest in 2012); I solved eighteen of the problems posed by the contest, achieving a rank of 10th (out of 155 participants).

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

Problem (E; medium difficulty):

Please improve my program

Santa has written a Python program for doing some calculations. However, he has poorly implemented the algorithm so that the program runs painfully slow.

Problem

Optimize the following python program so that it does run with reasonable speed. You can also implement the algorithm in a different language if you prefer. The range for the input values is between 1 and 1000000.

import sys,string

def magicnumber(n):
  for t in range(1,n+1):
    a=0
    b=0
    for k in range(2,t):
      c=1
      for i in range(2,k):
        if k%i==0:
          c=0
      b+=c
    for k in range(t+1,n+1):
      d=1
      for i in range(2,k):
        if k%i==0:
          d=0
      a+=d
    if a==b:
      return t
  return 0

print(magicnumber(int(sys.stdin.readline()))

Tipp: you can experiment with this program by pasting it into codepad.org

Example

Input

100

Output

41

Solution (E.java):

import java.util.Scanner;

public class E
{
  private static boolean is_prime[];

  public static void main( String p[] )
  {
    System.out.println( magicnumber( new Scanner( System.in ).nextInt()));
  }

  private static int magicnumber( int n )
  {
    is_prime = new boolean[ n + 1 ];
    for( int i = 3; i < is_prime.length; i += 2 )
      is_prime[ i ] = true;
    is_prime[ 0 ] = false;
    is_prime[ 1 ] = false;
    for( int i = 3; i < is_prime.length; i += 2 )
      if( is_prime[ i ] )
        for( int k = i + i; k < is_prime.length; k += i )
          is_prime[ k ] = false;

    for( int t = 1; t <= n; t ++ )
    {
      int a = 0, b = 0;
      for( int k = 2; k < t; k ++ )
      {
        int c = 1;
        if( !isPrime( k ))
        {
          final int k_cap = ( int )Math.sqrt( k );
          for( int i = 2; i <= k_cap; i ++ )
            if( k % i == 0 )
            {
              c = 0;
              break;
            }
        }
        b += c;
      }
      for( int k = t + 1; k <= n; k ++ )
      {
        int d = 1;
        if( !isPrime( k ))
        {
          final int k_cap = ( int )Math.sqrt( k );
          for( int i = 2; i <= k_cap; i ++ )
            if( k % i == 0 )
            {
              d = 0;
              break;
            }
        }
        a += d;
      }
      if( a == b )
        return t;
    }
    return 0;
  }

  private static boolean isPrime( int p )
  {
    if( p == 2 )
      return true;
    if( p % 2 == 0 )
      return false;
    return is_prime[ p ];
  }
}

Testing:

100
41
Advertisements


No Responses Yet to “E : Please improve my program”

  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: