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 and there are 168 primes less that N

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 $prime * $prime gt last

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. Wikibook Sieve with short cut $prime gt sqrt(last)

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.

4. Wikibook Sieve with short cut $prime gt sqrt(last) and primes as return rather than parameter

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.

5. Definition 1

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

6. Definition 2 optimized

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

7. Wikibook Sieve with short cut $prime * $prime gt last and primes as return rather than parameter with introducing a temp variable

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.

8. Wikibook Sieve with short cut $prime * $prime gt last and primes as return rather than parameter with introducing a temp variable N =50000

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.

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

10. Pekka's Sieve - 50,000

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

11. Quantifier not (some ..satisfies)

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

12. Quantifier every .. satisfies

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

14. Sieve using map:

Sieve algorithm using map This runs on BaseX but map and operators fold-left and idiv not known in exist 3.0