There are coins that are trying to do that. Primecoin for example is looking for prime numbers.
In any case mining is essential for bitcoin to work so you can't really call it a waste.
In any case mining is essential for bitcoin to work so you can't really call it a waste.
It can't be secure because all such work is preimageable because it has to be known to someone a priori. The Bitcoin proof-of-work can't be known a priori.
What exactly it can't be secure? The proof of work scheme that primecoin uses?
The reuseability of proof-of-work claims that it is unlikely that known primes can be reused.
However unlike strongly irreversible astronomical entropy quality of a block chain of cryptographic hashes in proof-of-work, I don't think we can be sure that the NSA or someone can't develop an algorithm that exploits factorization or some mathematical property of common factors for preimage attacks on searches for primes that are multiples of the block hash.
In short, I think there is too much mathematical order in the search for primes. Whereas cryptographic hash functions are designed to maximize entropy with diffusion and confusion.
It is not a risk I would be willing to take with my money, given for example that the NSA secretly had differential cryptoanalysis for a decade and could crack most encryption but the public didn't know it.
For example quantum computing breaks public-key cryptography based on discrete logarithm factorization, e.g. RSA. But it doesn't break cryptographic hashes, so Lamport signatures remain secure.
P.S. Also I doubt the security due to lack of botnet resistance.
.