For some number theory problems like finding Euler Totient Function for some number N,the method involves multiplying N by (1-1/p) for all primes p which divide N. This takes care of Inclusion Exclusion step as all additions/subtractions correspond to Inclusion/Exclusion step. However if the problem is modified to finding all numbers below K which are coprime to N, we cannot directly carry on the multiplications as some of the primes may not divide K completely and instead of this we have to carry on Integer divisions corresponding to each combination of prime divisors of N(2^x,if x prime divisors). So the solution which was linear in number of prime divisors is rendered exponential. Is their someway around this complication.
