Prime numbers are searched for doing the PoW. The blockchain essentially contains a data base with prime numbers. As far as I can tell Primecoin never was popular,.but I like the novel approach of doing things, when most cryptocurrencies of that time were lame copies.
Btw. the Primecoin creator made Peercoin, which was afaik the first (and apparently still running) network being secured by Proof-of-Stake.