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


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