HackerRank

1AC. 1D DP + Sieving

#include <cmath>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cctype>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <unordered_map>
using namespace std;

int ways(int n)
{
    if (n <= 1) return n;

    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < n; i++)
    {
        dp[i + 1] += dp[i];
        if ((i + 4) <= n) dp[i + 4] += dp[i];
    }
    return dp[n];
}

int cntPrimes(int n) // sieving
{
    vector<int> mark(n, 1);
    mark[0] = 0;

    int inx = 1; // 2
    int scnt = 1;
    while (inx < n && scnt > 0)
    {
        scnt = 0;
        for (int i = 2* inx + 1; i < n; i += (inx + 1))
        {
            mark[i] = 0;
            scnt++;
        }
        if (scnt > 0)
        {
            inx++;
            while (inx < n && mark[inx] == 0) inx++;
        }
    }

    return std::accumulate(mark.begin(), mark.end(), 0);
}

int main()
{
    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        int nCnt = ways(n);
        int ret = cntPrimes(nCnt);
        cout << ret << endl;
    }
    return 0;
}