Timeline for List of first n prime numbers most efficiently and in shortest code
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2017 at 12:41 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Apr 20, 2015 at 22:26 | comment | added | John Tromp |
The following is interesting in that it entirely avoids the use of numbers. So instead it outputs an infinite string of '.' and 'p' characters: let f='.';o c(x:y)=x:c y;z c(x:y)=f:c y;p n='p':ap fix p(o.n)in f:f:p z
|
|
| Aug 18, 2013 at 21:49 | comment | added | Will Ness |
one char less: from haskell.org/haskellwiki/Blow_your_mind by BMeph, March 2008: nubBy(((>1).).gcd)[2..]!
|
|
| Aug 11, 2012 at 13:00 | comment | added | walpen | I think the whole import thing, and whether an answer can just run in the REPL is a question for meta. Most of the Haskell answers I've seen are self standing, compiled programs, but I do not know if they have to be. | |
| Aug 10, 2012 at 8:03 | comment | added | Will Ness |
Hi, I think we can leave out the imports... let's say we use :m +Module, how this translates into code? It doesn't. In the mean time I followed your lead and posted something w/out main= ;) will add that now to my post.
|
|
| Aug 9, 2012 at 21:55 | history | edited | walpen | CC BY-SA 3.0 |
added 533 characters in body
|
| Jun 11, 2012 at 23:24 | comment | added | walpen | Oh, so now that makes sense. I tend to pretend that all math takes constant time out of laziness (I program in Haskell after all). | |
| Jun 11, 2012 at 22:19 | comment | added | Peter Taylor | BTW at 72 chars, if you're on the absolute cutting edge of primality testing, you'd have a score just short of 11 million. The rest of the current answers would be far far worse. | |
| Jun 11, 2012 at 22:11 | comment | added | Peter Taylor | I'm assuming (my Haskell is negligible, but I know how it would be natural to do it in SML...) that you're only doing trial division by smaller primes, in which case trial division on a P does O(P^0.5 / ln P) divisions. But if P has k bits, a division takes O(k^1.585) (Karatsuba) or O(k^2) (naïve) time, and you need to run through O(n lg n) numbers of length O(ln(n lg n)) bits. | |
| Jun 11, 2012 at 20:01 | comment | added | walpen | No, because that gives me a horrendous score :/. But I'm sure you're right. It just looked like trial division, and that's the time complexity of trial division (maybe, according to my poor reading comprehension of a possibly wrong source) so I picked that. For now I'll call my score NaN, that seems safe. | |
| Jun 11, 2012 at 11:50 | comment | added | Peter Taylor | Wouldn't the complexity be something like O((n ln n)^1.5 ln (n ln n)^0.585)? (Or O((n ln n)^1.5 ln (n ln n)) if Haskell uses naive division rather than, as I've assumed, Karatsuba) | |
| Jun 11, 2012 at 11:03 | history | edited | walpen | CC BY-SA 3.0 |
changed to reflect the answer needed.
|
| Jun 11, 2012 at 8:21 | comment | added | Optimus | @walpen I'am sorry I modified the rules without notification, please make the changes as you see fit | |
| Jun 11, 2012 at 6:23 | history | edited | walpen | CC BY-SA 3.0 |
added 191 characters in body
|
| Jun 11, 2012 at 6:01 | history | edited | walpen | CC BY-SA 3.0 |
deleted 2 characters in body
|
| Jun 11, 2012 at 5:11 | comment | added | beary605 | •primes cannot be generated by an inbuilt functon or through a library | |
| Jun 11, 2012 at 3:48 | history | answered | walpen | CC BY-SA 3.0 |