Red John is Back Time : O(n) Space : O(n) 1234567891011121314151617181920212223242526272829bool 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]];}