## Primes

Algorithms for computing primes. The first comes the XQuery Wikibook, the next three by Pekka KilpelĂ¤inen from the paper XQuery for Problem Solving Software Practice and Experience, 2011. The final two using quantified expressions come for other authors
Four of the algorithms are based the definition of a prime. The versions using quantified expressions are faster than the versions in Pekka's paper using a predicate. The optimised version using position() is particularly poor in this XQuery implementation. Pekka's Sieve algorithm using only one sequence is much faster then the original Wikibook algorithm, due to a smarter end-condition. Both Sieve algorithms use recursion and thus may be limited by stack-size, depending on whether tail-recursion optimisation is possible, which it is in both these algorithms in eXist.
N is 1000 unless otherwise stated.

### 1. Wikibook Sieve

Originally posted in the XQuery Wikibook this algorithm is based on the Sieve of Eratosthenes
The list of primes starts off empty, the list of numbers starts off with the integers. Each recursive call of local:sieve takes the first of the remaining integers as a new prime and reduces the list of integers to those not divisible by the prime. When the list of integers is exhausted, the list of primes is returned.

### 2. Wikibook Sieve with short cut

Sieve 1 redundantly checks for divisors until the list of candidates is exhausted. However all candidates when the first is greater than sqrt of the last number must be prime.

### 3. Definition 1 N=500

The definition of primes is 'integers greater than one which are not divisible by any other prime except itself'

### 4. Definition 2 optimized N= 500

In Definition 1 a number can only be a multiple of smaller numbers, so it is not necessary to test \$cand on numbers higher than \$cand

### 5. Pekka's Sieve

Another algorithm implementing the Sieve of Erostanes. This one is more subtle than the obvious form in the Wikibook algorithm. Here the sequence of primes is built from successive recursive calls passing the remaining candidate numbers, of with the first will be the next prime. The stopping rule is based on the fact that for numbers greater than the sqrt of the last number, all multiples have already been eliminated.

### 6. Pekka's Sieve - 10,0000

N= 10,000. Comparing the time with that for N=1000, this shows that the Sieve algorithm is nearly O(N)

### 7. Quantifier not (some ..satisfies)

Alternative version based on the definition using not(some ...satisfy). see Devx

### 8. Quantifier every .. satisfies

Alternative version based on the definition using every ...satisfy.