First of all,
I think you must be knowing that if your code is giving TLE then it doesn’t mean it is correct but takes too long. TLE simply means you exceeded the time limit. Your program never finished running in time  so Codechef has no idea whether it was going to print out the right results or not!
if your java code is giving WA it meas your c++ code will also give WA.
Now about your C++ code (I don’t know much about JAVA)
Loops: You are using too many loops (remember loops are lazy). For ex your code
void Calculate_primes() {
for (int i = 0; i <= MAX; i++) {
arr[i] = true;
}
It runs till 500000. you don’t need that you can use static int arr[some_no] to set a 0 value in array another option memset(arr).
How to resolve TLE ?
 Simply look at your code you are
using so many loops.
 Take some time and review your code.

(Important) long long makes your code slower. Use it Wisely
I think this approach can be used:
1> For each N get the square root of N.
2> Check if N is prime then answer 1
3> If not prime check till root N all the factors of N and store each new factors.
For Example : N=12
Root N = 3 (floor root N)
26=12
34 =12
So all the multiples of 12 are 1,2,3,4,6.
Please Upvote and mark it as your answer IF IT HELPED YOU.
Happy Coding