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: | 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: | 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!

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!]