Need help in these two problems

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

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

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