$\displaystyle 550=2*5^2*11$

Is there an efficient way to do this without just multiplying all the combinations of the canonical decomposition?

- Jul 18th 2010, 02:49 PMdwsmithNumber of positive integers less than 550 and relatively prime to 550
$\displaystyle 550=2*5^2*11$

Is there an efficient way to do this without just multiplying all the combinations of the canonical decomposition? - Jul 18th 2010, 02:55 PMundefined
Do you mean you want something more efficient than this?

$\displaystyle \displaystyle \varphi(550)= 550 \cdot \prod_{p|550} \left( 1-\frac{1}{p} \right) = 550\left( 1-\frac{1}{2} \right)\left( 1-\frac{1}{5} \right)\left( 1-\frac{1}{11} \right) = 200 $

If you're writing a program, then you can do a sieve. I don't know what else. - Jul 18th 2010, 02:57 PMdwsmith
I knew the phi function but I couldn't remember what it did. Thanks. I feel dumb now.