Here’s another problem to think about: For a given positive integer n (0 < n < 231) we need to find the number of such m that 1 ≤ m ≤ n, GCD(m, n) ≠ 1 and GCD(m, n) ≠ m. For example, for n = 6 we have only one such number m = 4.
The solution is to subtract from n the amount of numbers, coprime with it (its amount equals to φ(n)) and the amount of its divisors. But the number 1 simultaneously is coprime with n and is a divisor of n. So to obtain the difference we must add 1. If n = is a factorization of n, the number n has (a1 + 1) * (a2 + 1) * … * (ak + 1) divisors. So the answer to the problem for a given n equals to
n – φ(n) – (a1 + 1) * (a2 + 1) * … * (ak + 1) + 1