Can anybody help me with these two problems?

In the first problem, I am getting TLE for last sub task only. AC for rest,

In the second one, I am getting WA for first subtask. AC for rest.

Can anybody help me with these two problems?

In the first problem, I am getting TLE for last sub task only. AC for rest,

In the second one, I am getting WA for first subtask. AC for rest.

In the first task every time you check every prime number that is lower than the number.

This is not a good idea. It runs in O(x) for number = x.

You should use factorisation in O(sqrt(x)) or factor all numbers while doing the sieve and remember it O(NlogN).

How do I factor numbers while sieving? I am not able to understand. Can you elaborate a bit?

How to factor all numbers in [1,k] while doing the sieve in O(k log k)?

For each number in [1,k] keep a vector with its factors.

While doing the sieve, if you got prime number p just go through p*2, p*3, p*4, p*5, …

and add p to it’s vector.

For example if you found prime p = 7.

Add 7 to factors of 14,21,28,35,42,49,56,63,70,77 … (to the vectors)

The **additional** code in C++ should look like this (N is maximum):

```
vector<int> factors[N];
...
factors[p*k].push_back(p);
```