Red John is Back

• Time : O(n)
• Space : O(n)

c++

bool prime[222222];
 int psum[222222];
 
 void init() {
     memset(prime, true, sizeof prime);
     prime[0] = prime[1] = false;
     for(int i = 2; i * i <= 222222; i++) {
         if(prime[i]) {
             for(int j = i * i; j <= 222222; j += i)
                prime[j] = false;   
         }
         psum[i] = psum[i - 1] + prime[i];
     }
     for(int i = sqrt(222222); i < 222222; i++) {
         psum[i] = psum[i - 1] + prime[i];
     }
 }

int redJohn(int n) {
    vector<int> dp(5, 1);
    for(int i = n - 4; i >= 0; i--) {
        dp[0] = dp[1] + dp[4];
        dp[4] = dp[3];
        dp[3] = dp[2];
        dp[2] = dp[1];
        dp[1] = dp[0];
    }
    return psum[dp[0]];
}