Algorithms for computing primes. The first comes the XQuery Wikibook, the next three
by Pekka Kilpeläinen
from the paper XQuery for
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.
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
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
The definition of primes is 'integers greater than one which are not divisible
by any other prime except itself'
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
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.
N= 10,000. Comparing the time with that for N=1000, this shows that the Sieve algorithm is nearly O(N)
Alternative version based on the definition using not(some ...satisfy). see Devx
Alternative version based on the definition using every