I'm no mathematician, and I don't know of any probabilistic way to do it, but one option would be to build up a look up table of known primes. If you know the range the number to be tested lies in, that's an advantage. If you know the numbers to be tested will be in a fairly narrow range, all you have to do is store that range, and you can do a quick lookup to verify you numer is a prime or not. It's probably not that big a deal to bundle a couple of megabytes of prime numbers with your app to allow quick lookups, or perhaps to spawn a background process to calculate the list your application requires.

Another option is to keep a fairly small lookup file, and when checking numbers all you have to do is divide by all the numbers in your list. For example, if you store the primes from 2 to 1000, you will know that you can be sure that your test is reliable for any number up to 1000 * 1000 or one million. When you get above this figure, you'll still catch a lot of primes, but the accuracy will go down the further above the square of your top number you get. Increasing the number of primes in your table will increase the accuracy and range, but will also increase the number of divisions required.

I know this isn't the answer you're looking for, but I hope it helps.

Another option is to keep a fairly small lookup file, and when checking numbers all you have to do is divide by all the numbers in your list. For example, if you store the primes from 2 to 1000, you will know that you can be sure that your test is reliable for any number up to 1000 * 1000 or one million. When you get above this figure, you'll still catch a lot of primes, but the accuracy will go down the further above the square of your top number you get. Increasing the number of primes in your table will increase the accuracy and range, but will also increase the number of divisions required.

I know this isn't the answer you're looking for, but I hope it helps.