#10179 - Irreducable Basic Fractions

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
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 PHPGraphLib - Click For Official Site