Note: When I refer to “the number”, “our number”, or “p”, in the text below I’m probably referring to the number we want to examine (to see if it’s a prime or not).

This is a simple primality test. It’s built upon the worst possible test available: Try to divide the number with every single number between two and our number, and see if you find anything. This is a greatly improved version. By reducing the numbers we need to test, we can make the procedure considerably faster. First of all, we can test and see if the number is divisible with two, if it isn’t, then we only need to test odd integers from now on. This is obvious; however, we can reduce the numbers we have to try a lot more. Consider the following statement:

Claim: If an integer, p, isn’t divisible with x, then it isn’t divisible with any integer larger than p/x. This is, if p isn’t divisible with any integer smaller than x.

Proof: Assume that q divides p, and q > x. The quotient of these numbers are p/q. Then our claim must be correct, since p/q < p/x since q > x.

What does this mean in practice? It means that if we’ve tried to divide the number with 2, 3, 5 without result, then we only need to test every odd number between 5 and p/5. If we try to divide it with 7, without results, then we only need to test the numbers between 7 and p/7. And so on.

Here’s the script:


// Ask the user for a number.
var number, i, t;
number = get_string("Enter the number you want to test:", 0);
number = real(number);
// Primality test.

if (number == 2)
{
//It's the one and only odd prime!
show_message("Number " + string(number) + " is cool. It's a prime!";
exit;
}
else
{
if (number mod 2 == 0)
{
//It's an even integer.. Not a prime.
show_message("Number " + string(number) + " isn't that cool.. It's not a prime. You can divide it with 2.";
exit;
}
}
t = 1;
for (i = 3; i < number/t; i+=2)
{
if (number mod i == 0)
{
//It's possible to divide the number with i, hence it's not a prime.
show_message("Number " + string(number) + " isn't that cool.. It's not a prime. You can divide it with: " + string(i));
exit;
}
else
{
//We'll assign the value of i to t.
t = i;
}
}
//Nothing has been found.
show_message("Congratulations, you're number (" + string(number) + " is a prime!";


Ok, let’s discuss what we’ve done. First of all we determine if our number is two, if that’s the case, well, then it’s a prime. If it isn’t, we determine whether it’s divisible with two, if it is: Well, then it’s an even integer which can’t possibly be a prime. The good thing with this is that we’ve now excluded all even integers and only have to try the odd ones. The for-loop is quite easy to understand: We just test every integer that we have to test according to our claim in the beginning. If we don't find an integer to divide our number with, then it’s a prime.

If you have any questions, ask them and I’ll answer.


EDIT: I don't know why my indention is f*cked up, it looks correct in the editor.
EDIT2: I just noticed a slight improvement to the method, run the loop while i < number/(t+1) instead. You can compare the method to the more popular one, which is checking while i < sqrt(number). The methods are now equivalent.