HACKER RANK: Red John is Back

Problem Link: https://www.hackerrank.com/challenges/red-john-is-back

Summary:
Given N find number of ways to to arrange 4X1 and 1X4 bricks in 4XN block. Say there are M ways so print P number of prime up to M(i.e. <=M).

For Example:

Sample Input:
4
1
3

Sample Output:
0
3

For N=1
There is only one way so P = 0 as there is no prime number less than M=1

For N=7
there is M=5 ways so answer P=3 as 2,3,5 is less than than and equal to 5.

Topic:
Dynamic Programming Approach: https://en.wikipedia.org/wiki/Dynamic_programming

Logic:
What I have done is take number N as a block of weight N kg and try to adjust weight 1kg and 4kg weight in different ways.
So number of ways can be recursively computed as:
F(n) = F(n-1) + F(n-4)
if we place weight of 1kg then F(n-1) need to be computed.
if we place weight of 4kg then F(n-4) need to be computed.

Then taken sum of all computes M = F(n)

Now using Sieve Of Eratosthenes(http://www.geeksforgeeks.org/sieve-of-eratosthenes/) we compute P number of prime numbers up to M.

To View My Solution:
https://github.com/shivam04/hackerrank/blob/master/red-john-is-back.cpp