Efficiently doing prime factorisation by hand

Question

I have a yes/no question first (if 2 questions are allowed in 1 post).

When doing prime factorisation for using the Euler totient function can you use a particular prime more than once. (i.e. $p_{1} = 5, p_{2} = 3, p_{3} = 5$)?

What is the best way to do prime factorisation by hand? I have managed to factorise 1125 into $5 \cdot 5 \cdot 5 \cdot 3 \cdot 3$

However this is a small number and I managed to factorise it through intuition and no specific method.

What is an efficient way to do this by hand, and are the above prime factors correct?

Thanks for any answers in advance.

Answer 1

1. Regarding the totient, $\phi(mn)=\phi(m)\phi(n)$ only if $m,n$ are relatively prime. Hence not only may you use a prime more than once, you must pull out all copies of a prime, then treat them all together: $\phi(p^k)=p^k-p^{k-1}$.

2. Your factorization of $1125$ is correct, as is your strategy (divide by small primes as much as possible).