There are a lot of algorithms out there to help you deal with prime numbers. Here are a couple ordered by efficiency, the first being the most efficient. If you run the code in C, you'll notice there's a sharp drop in time consumption between the first and 3rd examples but that the change is very slight between the 3rd and 4th...
$n is the number we're trying to figure out whether it's prime or not...
- divide $n by all the numbers preceding it until you find a multiple of $n or until you run out of numbers
- Same method as above, but instead of going all the way to $n, you can solely consider all the numbers till 1+trunc(sqrt($n))...
-
Same method as above but exclude all the pair numbers (easily done by having a loop where the index is increased twice)
-
Same method as above plus store all the previous prime numbers you've already found and exclude their product...