Improve Execution Time

Question

How can the following program execution time improved. I have used dynamic programming in both "recursive" as well as "prime" function. But not getting the efficient execution time.

QUESTION:There is a wall of size 4xN in the victim's house where. The victim also has an infinite supply of bricks of size 4x1 and 1x4 in her house. In every configuration, the wall has to be completely covered using the bricks. Gale Bertram wants to know the total number of ways in which the bricks can be arranged on the wall so that a new configuration arises every time. Let the number of Configuration = M.

So, he wants Patrick to calculate the number of prime numbers (say P) up to M (i.e. <= M). You are required to help Patrick correctly solve the puzzle.

Sample Input The first line of input will contain an integer T followed by T lines each containing an integer N.

Sample Output Print exactly one line of output for each test case. The output should contain the number P. Constraints 1<=T<=20 1<=N<=40

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class Solution{
    public static int[] b = new int[217287];
    public static void main(String[] args){
        Scanner stdin = new Scanner(System.in);
    int t = stdin.nextInt();
    int[] a = new int[41];
    for(int j=0;j<4;j++){
            a[j] = 1;          //till n<=3, number of possiblities = 1. These will work as base cases.
        }
        a[4] = 2;
    for(int x=0;x<t;x++){
        int n = stdin.nextInt();
        for(int i=5;i<=n;i++){
            a[i] = -1;         //initialise all value in the array as -1.
        }
        if(n<4)
            System.out.println("0"); // if n<4, number of possibilities =1. So no prime number before that is 0.
        else{
                     //for n=4, possibilities = 2. This is a base case.
        int num1 = recursive(a,n);          // storing number of possibilities in num1.
        int num2 = prime(num1);    //calling to calculate number of prime numbers before or equal to num1.
        System.out.println(num2);
        }
    }
}
public static int recursive(int[] a, int n){
    if(a[n]!=-1)                             // retrieving a[n] value if already calculated.
        return a[n];
    else{
        a[n] = recursive(a,n-1) + recursive(a,n-4); // calling recursively.If we fill with a 4*1 first tile then number 
                                                    //tiles left is n-1(try visualising).If we fill 1*4 tile first
                                                    // we have n-4 tile left.
        return a[n];
    }
}
public static int prime(int n){
    int count = 0;
    if(b[n]!=0)
        return b[n];
    else{
    for(int i=2;i<=n;i++){
        if(b[i]!=0){
            count = b[i];
        }
        else{
        int flag = 0;           
        for(int j=2;j<=i/2;j++){
            if(i%j==0){
                flag = 1;
                break;
                }
            }
    if(flag==0){
        count++;
        b[i]=count;
    }
    }
    }
    return count;
    }
}

}

I got a timeout(more than 4s) for the following input. 20 35 23 25 38 4 35 19 8 23 35 3 36 12 10 30 13 18 31 40 37

Answer 1

You may want to further optimize your int prime(int n) function. (Of course, you can use any efficient algorithm from the 'net, but:) To avoid doing the same calculations again and again note that you can compute prime(n+m) faster if you already have prime(n).

(I think you were already thinking in that direction because you are using some 'cache' for already calculated figures.)

Edit: See Ordous' answer #2 :)

Edit2:

To elaborate a little more on the idea:

Q: If I know the number c of primes <= X, what is the number of primes <= (X+1)?

A: c, if X+1 is not a prime, or c+1 if X+1 is a prime. Like so:

public static int prime2( final int n ) {
    int count;
    if ( n <= 2 ) {
        count = 1;
    } else {
        count = prime2(n-1);
        if ( isPrime(n) ) {
            count = count + 1;
        }
    }
    return count;
}

Then add your caching approach to store the result of any computed prime2(x) for later use.