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.
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|
This script will hole whether the candidate
n is prime or not in the variable
|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  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)) = > then set [result v] to [false] // Not prime. stop [this script v] end change [factor being tested v] by  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.