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 
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.

Cookies help us deliver our services. By using our services, you agree to our use of cookies.