I've actually written a small program (it was for a homework assignment in a college Java class I took) that actually checked for Prime numbers, and did it fairly quickly.
In fact, I found a list of primes in the range of two to the max integer value (used a Google search). I was able to iterate over the values (starting at 2), evaluate whether or not it was prime, and if it was, write it to a file. That all happened in under a second.
Here's a hint:
Use a square root. If the number you're checking (say, 25) has a whole number, integer square root (square root of 25 is 5), then the number you're checking is not, by definition, prime. If the number you're checking has a decimal square root, to check to see if it is prime, all you have to do is iterate, dividing the number you're checking by the next number in line.
As an example, sqrt(101) = 10.0498756
So take 101, and divide it by 2, 3, 4, up to 10. If it divides by any of those evenly
, then it's not prime.
There are other tricks, but I think this will help you get started.
Also, recall the the only even prime number is 2.