Sort 10 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;
if we see here from the description table ,the prime no. has more no. of relative primes.
1 is considered as relative prime for every no.
for n/phi(n) should be large ,phi(n) should be small and n should be large.
just consider n as product of prime no.and check whether its smaller than the given limit.
phi(n)=n*(1-(1/p)), where p is prime.
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
That would be equally easy. Think hard about khoangcachxalam1's observation, then what happens for composite numbers, and finally about how that observation behaves as the prime p approaches infinity (for a rigorous proof). This led me to find a solution with no non-input array exceeding length 15 despite N going up to 1e18.
Though long integers are needed ephemerally for very large N, I even avoided float arrays! If you are more experimentally minded, generate a table of n / phi(n) for 1 < n < 212 and watch what happens to those floats — that's what I did, just to make sure.
n / phi(n)
1 < n < 212
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