HackerEarth The maximum value problem solution

In this HackerEarth The maximum value problem solution You are given an integer N. For each integer i from 2 to N, assign a positive integer A[i] such that the following conditions hold:

For any pair of integers (i,j), if i and j are co-prime, then A[i] != A[j].

The maximum value among all A[i] is the minimum possible.

Find the maximum value among all A[i]'s.

HackerEarth The maximum value problem solution.

#include <bits/stdc++.h>
using namespace std;
int ans[100005];

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n,c=0;
        scanf("%d",&n);
        memset(ans, 0, sizeof(ans));
        int answer = 0;
        for (int i=2;i<=n;i++)
        {
            if (!ans[i])
            {
                ans[i]=++c;
                for (int j=i;j<=n;j+=i)
                ans[j]=ans[i];
            }
            answer = max(answer, ans[i]);
        }
        cout << answer << endl;
    }
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5, B = 62;
int t, n;
bool pr[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        int ans = 0;
        for (int i = 2; i <= n; ++i)
            if (!pr[i]) {
                ++ans;

                for (int j = 2 * i; j <= n; j += i) {
                    pr[j] = true;
                }
            }
        cout << ans << '\n';
    }
}