A whole number is prime if it is positive and has exactly 2 factors (itself and "1"). A factor of an arbitrary number "n" is a number that divides into "n" without leaving a remainder. This tutorial explains how to check if a number is prime.

Methods of Detection

There is an infinite number of prime numbers (this can be proven using Euclid's theorem), which means storing a list of all prime numbers is impossible and, as such, one may need to verify the primality of a number dynamically. There are several methods to do this.

Trial Division

When factoring a number, its factors will come in pairs (unless it is a perfect square — in which case its square root will lack a pair). For example, the number 12's factors are 1 ↔ 12, 2 ↔ 6, and 3 ↔ 4. If 1, 2, and 3 are not factors of 12, then its pairs won't be either. Using this, testing is only needed if numbers in the range 2 through the square root of n (inclusive) are factors of n, to test if n is prime. (In fact, only the prime numbers in that range have to be tested).

Trial division tests if a number is prime by checking how many factors the number has by dividing each possible factor into the number being tested for primality. One can use the () mod () block to test if a number is a factor of another number (by comparing the block's result to 0). Once a factor in the range mentioned earlier is found, the number is not prime, and so the script can be stopped without needing to check other factors.

Note Note: If prime numbers are being generated sequentially, the script below should be adapted to only test the prime numbers that have already been generated as factors for the candidate

Script

This script will hole whether the candidate n is prime or not in the variable result.

Note Note: It is highly recommended, but not required, that the block is run with the option "Run without screen refresh" set, especially with larger numbers being tested.
define (n) is prime?
set [factor being tested v] to [2]
set [result v] to [true] // Assume the number is prime, and corrects itself if wrong
if <(n) < (2)> then // The number cannot be prime
set [result v] to [false]
else
repeat until <(factor being tested) > ([sqrt v] of (n))>
if <((n) mod (factor being tested)) = [0]> then
set [result v] to [false] // Not prime.
stop [this script v]
end
change [factor being tested v] by [1]
end
end

Finding a List of Prime Numbers

When finding a list of prime numbers, as opposed to checking if a certain number is prime, use this script:

When green flag clicked
delete all of [Prime Numbers v]
delete all of [Composite Numbers v]
set [j v] to (2)
forever
    set [k v] to (2)
    repeat until <<(k)= (j)> or <((j) mod (k))= (0)>>
        change [k v] by (1)
    end
if <(k)=(j)> then
    add (j) to [Prime Numbers v]
else
    add (j) to [Composite Numbers v]
end
change [j v] by (1)

This will generate a list of prime numbers in the prime numbers list and a list of composite numbers in the composites list. This script will run faster than the one above because only prime numbers need to be checked.

Mersenne Primes

Mersenne Primes are primes that take the form of where is a positive integer. They were named after a 17th century Frenchman, Marin Mersenne, who studied them.

Checking the primality of Mersenne numbers: Lucas-Lehmer

The Lucas-Lehmer primality test is a sequence of numbers (the Lucas-Lehmer sequence) that is defined as follows:

This means that for a given :

  • If is 0, then equals 4;
  • Otherwise, is given by , recursing because is dependent on

Now you've got the Lucas-Lehmer sequence, you can check whether a particular Mersenne Number is prime.
1. Extract the exponent from your Mersenne number (the in )
2. Find the number in the Lucas-Lehmer sequence that is one below the from Step 1 ()
3. If the number from step 2 () is an exact multiple of your Mersenne number, it is a Mersenne prime!

Note Example: For the Mersenne prime 7 (), the exponent is 3, and the 2nd Lucas-Lehmer number is 14. Because 14 is an exact multiple of 7, 7 is prime.

Scratch Implementation

There is a flaw in this method. Lucas-Lehmer numbers get astronomically big astronomicallly quickly (the 5th number in the sequence is 1.4 billion). However, there is a solution: Lucas-Lehmer still works if you modulo the result. If you do so, appling Lucas-Lehmer and modulating still works for the next number. Therefore, a revised Lucas-Lehmer method is presented here
To generate revised Lucas-Lehmer:

define Lucas-Lehmer (n) (mersenne number) // returns the nth lucas-lehmer number, modulated by the mersenne number
if <(n) = [0]> then
set [lucas lehmer number v] to (4)
else
Lucas-Lehmer ((n) - (1)) (mersenne number)
end
set [lucas lehmer number v] to ((((lucas lehmer number) * (lucas lehmer number)) - (2)) mod (mersenne number))

To check if a number is prime:

define Mersenne_Checker (mersenne number) (mersenne exponent)
Lucas-Lehmer ((mersenne exponent) - (1)) (mersenne number) :: custom
if <(lucas lehmer number) = [0]> then
say [It is a prime!]
else
say [It is not a prime!]
Cookies help us deliver our services. By using our services, you agree to our use of cookies.