<h2>GolfScript (45 chars, score claimed ~7708)</h2>

    ~[]2{..3${1$\%!}?={.@\+\}{;}if)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, in GolfScript adding an element to an array requires copying the array. I've optimised this to copy the list of primes only when it finds a new prime, so only `n` times in total. Each copy operation is `O(n)` items of size `O(ln(n ln n)) = O(ln n)`&dagger;, giving `O(n^2 ln n)`.

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

&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...