the Prime Sieve in XQuery

I guess I've been putting my spare effort over the past few months into the Wikibook on XQuery, so the blog has been very neglected.

I've learnt a lot in writing the example code in the Wikibook. The other day I bumped in the Euler Project and started on the first few the problems. Problem 3 is about primes so I had to write a prime number generator. The Sieve of Eratosthenes in XQuery is so simple and obvious:


declare function local:sieve($primes,$nums) {
if (exists($nums))
then
let $prime := $nums[1]
return local:sieve(($primes,$prime), $nums[. mod $prime != 0])
else $primes
};

local:sieve((),2 to 1000)

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.

Lovely but sadly not very practical for the size of numbers in the problem.

Discussion and execution are in the Wikibook.