Sort 9 Discussions, By:
Please Login in order to post a comment
attention : if p is prime
p^k/phi(p^k) = p^(k-1)/phi(p^(k-1))=...= p/p-1;
I wonder how people would attempt to solve this problem if the ratio itself is required as part of the output.
I did it on projecteuler when I first solved the problem. Hint is sieve, fast and easy :)
Edit: Just checked it with (10**18)**0.5 (10**9) and it caused memory error, with so big upper bound I guess time limit will never enough.
As @tieros suggests sieve is fine for 10^6 input, but for higher n, we can directly find the factors of the given ans (as the ans can be found in O(1) time). Time complexity would be dependent on the time taken to find factors O(sqrt(N)) as per Factors time complexity
what is runtime error
TCs 4, 5, 7 are failing with Wrong Answer. Any ideas what could be wrong?
If you solve the original PE problem you will get the solution there itself
Hmmm. Any extra tricks on TC#6? I only get wrong answer on that one.
'Find the value of n < N...' meaning N excluded:D
Can we get test cases which are being executed here, I am able to see results for all the possible test cases in my local. and they seem to paas. But when i submit it says runtime error, time out etc. Can we get list of testcases that system is trying run ?
Any idea what could be there in test cases 3,4,5 and 6? I did prog in python and getting runtime errors. thx
I'd guess you have a for loop that exceeds 10^8. I haven't actually managed to pinpoint the exact cutoff, but its somwhere between 10^7 + 5*10^6 and 10^7 + 6*10^6.
No more comments