Calculating the number of prime numbers to solve the puzzle How can the following program execution time improved?  I have used dynamic programming in both "recursive" as well as "prime" function, but I'm not getting the efficient execution time.


  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. \$&lt;= 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 &lt;= T &lt;= 20\$
  \$1 &lt;= N &lt;= 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]; //array initialized before because the value remains same.
        for(int j=0;j&lt;4;j++){
                a[j] = 1;          //till n&lt;=3, number of possiblities = 1. These will work as base cases.
            }
            a[4] = 2;
        for(int x=0;x&lt;t;x++){
            int n = stdin.nextInt();
            for(int i=5;i&lt;=n;i++){
                a[i] = -1;         //initialise all value in the array as -1.
            }
            if(n&lt;4)
                System.out.println("0"); // if n&lt;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&lt;=n;i++){
            if(b[i]!=0){
                count = b[i];
            }
            else{
            int flag = 0;           
            for(int j=2;j&lt;=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
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;


Clean up those imports. Importing everything in a package is a bad idea, as it might easily lead to conflicts between same named classes. Also it is hard to see what is actually used.



You ain't got a package defined, define one.



class Solution{


That's a not very good class name. Classes should be named after what purpose they serve, or what purpose the methods contained within the class serve.



public static int[] b = new int[217287];


Here is the ultimate rule for variable naming:


  You're only entitled to use one character variable names if you're dealing with dimensions (x, y, z). Second best is you're allowed to use one character variable names in simple for loops (i, j, k)...but the last point is up for debate and it should not be the case.


And here is a simple guide for naming variables:


  Name variables after what they contain. You're not allowed to use one character variables except when dealing with dimensions.


Why is it so important to name variables after what they do? Well, quick, tell me what this code does:
 if (b[n] != 0).



for(int x=0;x&lt;t;x++){


This is even worse. x is normally only used for the dimension, so unless you're looping over the x dimension of something here, this variable should be called different and according to what it does.



for(int i=0;i&lt;=n;i++){
    a[i] = -1;         //initialise all value in the array as -1.
}


Only comment things that are not obvious from the code. In this case I can see that the array is initialized to -1...or I could see it if the variables would have fitting names:

for (int index = 0; index &lt; a.length; index++) {
    a[index] = -1;
}


Note that a is still not a good name. Also what I do not see from the code at this point is why it is initialized to that value. So if to comment something, then the why is interesting.



if(n&lt;4)
    System.out.println("0"); // if n&lt;4, number of possibilities =1. So no prime number before that is 0.
else{


You should not omit braces from ifs and fors, even one line once. It can be very confusing in the long run.



else{
for(int j=0;j&lt;4;j++){
    a[j] = 1;          //till n&lt;=3, number of possiblities = 1. These will work as base cases.
}
a[4] = 2;             //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);
}


Why are your else branches not indented?



public static int recursive(int[] a, int n){


That's another not very good name. Functions should be verbs, not adjectives. They have a function, not a state, and the name should mirror that function.



You have no JavaDoc in there, fix that.



Consider using a code formatter, and then consider using more blank lines and more whitespace to make the code easier readable.