Return to Answer

GolfScript (43 chars, score claimed 26157)

~[]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)†. 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)†, 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.

† O(ln (n ln n)) = O(ln n + ln ln n) = O(ln n). I should have spotted this before commenting on various posts...

GolfScript (45 chars, score claimed ~7708)

~[]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)†. 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)†, giving O(n^2 ln n).

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

† O(ln (n ln n)) = O(ln n + ln ln n) = O(ln n). I should have spotted this before commenting on various posts...

GolfScript (43 chars, score claimed 1125000)

~[]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). 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, giving O(n^3 (ln n)^2).

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

GolfScript (43 chars, score claimed 26157)

~[]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)†. 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)†, 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.

† O(ln (n ln n)) = O(ln n + ln ln n) = O(ln n). I should have spotted this before commenting on various posts...

GolfScript (43 chars, score claimed 323.46)

~[]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). 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, giving O(n^2 ln n).

GolfScript (43 chars, score claimed 1125000)

~[]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). 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, giving O(n^3 (ln n)^2).

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