#10179 - Irreducable Basic Fractions
|Solution Description: ||Basically, for a given integer n, we want to know how many numbers < n are co-prime with n. Luckily, there's a function that does exactly that: Euler's totient (phi) function.|
phi(n) = n * [(1 - 1/p) for all primes p such that p|n]
So, factor n, and use the prime factors to computer phi(n).
Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By