Say the message $M$ is a product of one of the primes $p$ or $q$, won't the $gcd$ of $M$ and $n$ (the public encryption key) give me $p$ or $q$?
say $p = 11$ $q=19$ $n=11*19=209$ and $M=33$.
$gcd(33, 209) = 11$. and I know that if the $gcd$ isn't $1$ then it's one of the primes..
Because $gcd's$ running time is very fast, I can just try and do this with every message I send.. What am I missing?