# Thread: Number of positive integers less than 550 and relatively prime to 550

1. ## Number of positive integers less than 550 and relatively prime to 550

$550=2*5^2*11$

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

2. Originally Posted by dwsmith
$550=2*5^2*11$

Is there an efficient way to do this without just multiplying all the combinations of the canonical decomposition?
Do you mean you want something more efficient than this?

$\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.

3. I knew the phi function but I couldn't remember what it did. Thanks. I feel dumb now.