A proof concering $\Re(\log\zeta(\sigma+it))$

I have been trying to prove that $$\Re(\log\zeta(\sigma+it))=\sum_{n=2}^\infty\frac{\Lambda(n)}{n^\sigma\log n}\cos(t\log n),$$ but now I've given up, so I looked up the answer in the back of the book. It starts just the same way I was trying to go:

\begin{align*} \log\zeta(s)&=-\sum_p\log\left(1-\frac{1}{p^s}\right) \\ &=\sum_p\sum_{k=1}^\infty\frac{1}{kp^{ks}}. \end{align*}

But then the author just jumps right to the solution, not giving any intermediary step(s):

$$\sum_p\sum_{k=1}^\infty\frac{1}{kp^{ks}}=\sum_{n=1}^\infty\frac{\Lambda(n)}{n^\sigma\log n}\{\cos(t\log n)-i\sin(t\log n)\}.$$

Start by writing $p^{-ks}$ as $\exp(-ks \log p)$, where $s = \sigma + it$. –  Erick Wong Jan 28 '13 at 6:42
You are familiar with Euler's formula, no? Also, it might help to work from the right and replace the summation over $n$ with summation over prime powers $p^k$ (all other terms are $0$ thanks to the $\Lambda(n)$). –  Erick Wong Jan 28 '13 at 16:22