Difference between revisions of "Talk:99 questions/Solutions/35"
Jump to navigation
Jump to search
(New page: The last change to the code brought its complexity down to the theoretical one of trial division, as it should be, about O(n^1.45) empirically, in number of primes produced; previous versi...) |
|||
Line 1: | Line 1: | ||
The last change to the code brought its complexity down to the theoretical one of trial division, as it should be, about O(n^1.45) empirically, in number of primes produced; previous versions had it up there in O(n^1.67) or even O(n^1.85), which is what I've started from. [[User:WillNess|WillNess]] 12:02, 31 May 2011 (UTC) |
The last change to the code brought its complexity down to the theoretical one of trial division, as it should be, about O(n^1.45) empirically, in number of primes produced; previous versions had it up there in O(n^1.67) or even O(n^1.85), which is what I've started from. [[User:WillNess|WillNess]] 12:02, 31 May 2011 (UTC) |
||
+ | : this refers to using <code>filter (\n-> n==head(factor primes n))</code> instead of <code>filter (null . tail . factor primes) </code>. But actually the ''external'' faster-produced primes list of Q.31 should just be used. [[User:WillNess|WillNess]] 23:55, 4 June 2011 (UTC) |
Latest revision as of 23:55, 4 June 2011
The last change to the code brought its complexity down to the theoretical one of trial division, as it should be, about O(n^1.45) empirically, in number of primes produced; previous versions had it up there in O(n^1.67) or even O(n^1.85), which is what I've started from. WillNess 12:02, 31 May 2011 (UTC)
- this refers to using
filter (\n-> n==head(factor primes n))
instead offilter (null . tail . factor primes)
. But actually the external faster-produced primes list of Q.31 should just be used. WillNess 23:55, 4 June 2011 (UTC)