how to solve 2nd problem helping hand?? please help

Precompute all primes till 1000000. Store them in a vector (sorted). For each n, binary search the number of primes less than or equal to n. Call that number p.

The answer is n+p-3.

## Edge cases

If n is 1 or 2, print n-1.

## Code

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector <int> f(1e6+1, 1), p(0);
for (int i = 2; i <= 1e6; ++i) for (int j = i; j <= 1e6; j += i) f[j]++;
for (int i = 2; i <= 1e6; ++i) if (f[i] == 2) p.push_back(i);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
auto ans = lower_bound(begin(p), end(p), n+1)-begin(p);
cout << (n == 1 || n == 2? n-1 : n+ans-3) << '\n';
}
}
```

Instead of binary search you can keep prefix array

can you explain for 8 why ans is 9 please

Why this approach, can you explain a bit please.

let l= no. of primes upto n then ans=l+n-3

`lower_bound()`

has a short implementation (and the vector was sorted ;)). Also, how exactly did you use prefix array?

Can you help with the 1st problem as well? Thanks in advance.

could you explain how the output is 8 for n=7

Just greedy and do what the problem statement says.

```
int main()
{
usaco();
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector <int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
sort(rbegin(a), rend(a));
if (n == 1) cout << "first\n";
else if (n == 2) {
if (a[0] == a[1]) cout << "draw\n";
else cout << "first\n";
} else {
long long x = 0, y = 0;
x += a[0];
y += a[1]+a[2];
for (int i = 3; i < n; i += 2) x += a[i];
for (int i = 4; i < n; i += 2) y += a[i];
if (x > y) cout << "first\n";
else if (x < y) cout << "second\n";
else cout << "draw\n";
}
}
}
```

making the prefix array like : ` pref[ i ] = pref[ i-1 ] + prime[ i ];`

There are 4 primes less than 8. The answer is 8+4-3 = 9.

precompute the no of primes for each i (1 to n) also then you dont need binary search and can answer query in O(1) time instead of logn.

here is link to my code:

https://www.codechef.com/viewsolution/36681721

yes mine is coming 7

1 2 3 4 5 6 7

LCM(4,5)=20;

LCM(6,7)=42;

1 2 3 20 20 42 4 2

LCM(20,42);

LCM(20,42)=420;

1 2 3 420 420 420 420

4 + 3 = 7 operations.

can anybody tell where i am wrong

Can you please give derivation for the formula

yeah even Im getting it that way

Why this method but ?

And how did u think of this approach ?

If you write down all numbers from 1 to n, you will notice that only the highest multiple of primes contribute to the LCM. Let’s say that there are p such numbers. It is optimal to convert these to the LCM first rather than the other numbers. In p-1 operations, you can make the last and second-to-last numbers equal to the LCM. Then we can make the other n-p+p-2 = n-2 numbers equal to the LCM. We also used p-1 operations to make the last number equal. So

the formula is p-1+n-2 = n+p-3

The edge cases are n = 1, \ 2.

can you guys tell me how you got this approach for Helping hand question???