# 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';    }}`