How can I find number of divisors of N which are not divisible by K.
($2 \leq N$, $k \leq 10^{15})$
One of the most easiest approach which I have thought is to first calculate total number of divisors of 'n' using prime factorization (by Sieve of Eratosthenes) of n and then subtract from it the Number of divisors of the number 'n' that are also divisible by 'k'.
In order to calculate total number of divisors of number n that are also divisible by 'k' I will have to find the total number of divisors of (n/k) which can be also done by its prime factorization.
My problem is that since n and k can be very large, doing prime factorization twice is very time consuming.
Please suggest me some another approach which requires me to do prime factorization once.