Do you really need to PROVE that the number is prime?
It is much easier to demonstrate that a number is NOT prime.
And, in many cases, eliminating nonprimes to find a "probable prime" is quite adequate. If a number cannot be proven to be nonprime with a reasonable effort, often you can use the number as if it were prime.
