# Prime Number Computation

## Collecting the primes

`sieve` returns a list of prime numbers up to its argument, n. It starts with a queue containing just the value 2, and iterates through odd numbers from 3 until n is reached. Any which are found to be prime are added to the end of the queue. A queue is used instead of a list to ensure that values in the returned list are in the correct order. In the Lisp dialect Emblem, this is:

```(defun sieve (n)
(do ((i 3 (+ i 2))
(q (queueFromList (list 2))
(if (primeP i (elemsOfQueue q))
(putOnQueue i q)
q)))
((< n i) (elemsOfQueue q)))))
```

## Balancing the inputs

By inspection, it can be verified that each vertex's inputs receives the same number of values, as follows:

 Senders Input Count Vertex Output Count ingate 1 `valve+` 1 `valve+` 1 `list` 1 `list` 1 `queueFromList` 1 `valve+``queueFromList` 1 `start+` N ingate`start+` N `<` N `<``start+` N `when+` (from `<`) 1 `<``start+` N `unless+` (from `<`) N-1 `when+` 1 `elemsOfQueue` 1 `unless+` N-1 `+` N-1 `unless+` N-1 `elemsOfQueue` N-1 `unless+``elemsOfQueue` N-1 `primeP` N-1 `primeP``unless+` N-1 `when+` P `primeP``unless+` N-1 `unless+` N-1-P `when+` P `putOnQueue` P `+``putOnQueue` and `unless+` N-1 `repeat+` 0

### Bugs to avoid

The likeliest bug is not feeding back the unaltered queue in the slave loop if the number isn't prime. Next, if the second input of `>` in the master loop is not sticky, it would only execute once, as it is injected into the loop from outside and would be immediately consumed. Thirdly, as list structure used in the queue of primes is destructively modified (added to) when `putOnQueue` is called, it is essential to initialize it with a fresh list by calling `list`. Finally, it is important to verify that the inputs on each vertex are balanced.

## Testing the primes The first input value of `primeP` is the number being tested, and the second is the list of primes less than it. As `primeP` is only required inside `sieve`, it only needs to test numbers which haven't been tested yet. As all the numbers less than the number we're currently testing will already have been tested, we already have all the primes we need. (Actually more than we need, since when testing a number for primeness, we only need primes up to its square root.)

`primeP` iterates through the list of primes, and if one exactly divides the number (its remainder is zero), the number is not a prime, and `primeP` returns `NIL`. Otherwise, if a prime squared is greater than the number, we've checked all the primes on the list we need to, and none was an exact divisor, so we return `T`.

For clarity, in the Lisp shown below, the expression `(zerop (mod i (car primes)))` to test if the remainder is zero was repeated. A temporary variable could have been used instead. In the Full Metal Jacket code, we simply added another edge from the `not` vertex. Finally, two sticky values were needed as a value was being injected into a loop.

```(defun primeP (i listOfPrimes)
(do ((primes listOfPrimes (cdr primes)))
((or (zerop (mod i (car primes)))
(> (* (car primes) (car primes)) i))
(not (zerop (mod i (car primes)))))))
```

Two call to `primeP`, followed by one to `sieve` are shown, followed by their output.  