8
$\begingroup$

Is there any efficient way , to find for a particular n, the cardinality of set consisting of all numbers coprimes to n, but bigger than m(assuming i know the prime factorisation of n and m)

I am looking for the implementation which is simple+fast (like the euler totient/phi function, which given the factorisation of n will just need O(logn) steps).

2 Answers 2