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.

## Methods of Detection

There are an infinite amount 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.