<h2>GolfScript (43 chars, score claimed 26157)</h2>

    ~[]2{..3$\+{1$\%!}?={\1$+\}*)1$,3$<}do;\;n*

This does simple trial division by primes. If near the cutting edge of Ruby (i.e. using 1.9.3.0) the arithmetic uses Toom-Cook 3 multiplication, so a trial division is O(n^1.465) and the overall cost of the divisions is `O((n ln n)^1.5 ln (n ln n)^0.465) = O(n^1.5 (ln n)^1.965)`&dagger;. However, due to the nature of GolfScript there's quite a bit of copying, and the cost is dominated by the need to copy the list of primes. That happens `O(n ln n)` times, and each copy operation is `O(n)` items of size `O(ln(n ln n)) = O(ln n)`&dagger;, giving `O((n ln n)^2)`.

And this, boys and girls, is why GolfScript is used for golfing rather than for serious programming.

NB I have an untested improvement

    ~[]2{..3${1$\%!}?>{@\+\}*)1$,3$<}do;\;n*

which avoids copying the list of primes except when it adds a prime to it, bringing the complexity down to `O(n^2 ln n)` and scoring ~5902. It's timing out on w0lf's online tester, so I suspect it's buggy, but it's not even managing to output debug info.

&dagger; `O(ln (n ln n)) = O(ln n + ln ln n) = O(ln n)`. I should have spotted this before commenting on various posts...