Need help in these two problems

general
1

Can anybody help me with these two problems?

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

Problem
My solution

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

Problem
My solution

2

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).

3

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

4

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 p2, p3, p4, p5, …
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);