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