oops! I observed that, in this solution he freed the memory before returning, so freeing variable memory does not count in the final results?
I always thought they calculate the total memory used on the runtime for entire execution and result displays the maximum memory required.
Instead of finding primes, you could have found lowest prime factor of each number.
https://discuss.codechef.com/questions/76818/prime-factorization-of-large-numbers
I also applied sieve for 10000000 but i think the complexity is n log(log(n)) and it should work as it is less than 10^8
@bhishma - How did you create an array of 10^7 elements? I thought of this same thing, but dropped the idea as C++ doesn’t allow creation of int arrays of more than 2*10^6 I think.
I coded in java , and as far as I know we could create arrays of size 10^8 without any issues.
@s1d_3: Stack limit can kill static arrays. Did you actually try submitting a code with a vector<> of that size?
That equivalently means that the result for a number ‘n’ is equal to the product of the result of two numbers ‘n1’ and ‘n2’ iff gcd(n1, n2)=1 i.e. they are coprime.
If n1 and n2 are further represented as the product of two coprime numbers, you eventually reach at the numbers that are “powers of a single prime”.
Now the only task is “how to calculate the result for numbers, which are powers of a single prime?”
This is fairly simple and can be done by summing the phi(d).d for every divisor d of that number.
Have a look on this solution :
The basic approach for any problem is to think of the possible solution and observing the patterns while keeping the constraints in the mind at the same time.
When you get some approach, think about it and try to prove the correctness, if you’re not able to prove the correctness, try to find a counter example, if you’re not able to find one, never hesitate to implement the approach in long challenges. At the end, long challenge will teach you a lot.
@xariniov9
Thanks,I understand how to calculate the answer.I am unable to arrive at the proof can you please simplify the proof.
You can actually use result 2 to come up with a faster solution which will basically compute the answer for all n in [1..n] in linear time.
Since \sum d . \phi(d) is a multiplicative function, we can use the concept mentioned here [Tutorial] Math note — linear sieve - Codeforces
My submission: CodeChef: Practical coding for everyone