Thread: What is an algorithm for finding out if a number is prime expressed in java?

This is for a Java project, I've been searching but cant find anything simple enough.

The simplest is to divide by integers starting with 2 up to the square root of that number.

You can be a little more clever if you know primes (you can just divide by primes up to that number). For example, if it's divisible by 8, it's also divisible by two, so you can skip 8.

For smaller numbers, you can also use a "Sieve of Erasthenes"

I suggest the Miller-Rabin primality test. It's a very fast probabilistic test, but around 1/4 of composite numbers will pass each round of the test (false positives for primality). Therefore, you should run 20 or 30 tests on each number. The probability that a composite number will get past 20 trials is less than (1/4)^20, i.e., very small.

Here's the algorithm:
http://en.wikipedia.org/wiki/Miller-Rabin_primality_test#Algorithm_and_running_time

It's only pseudocode, but if Java has the high-level integer arithmetic I think it does, it should be relatively easy to code.