in reply to (tye)Re2: (Golf): Sieve of Eratosthenes
in thread (Golf): Sieve of Eratosthenes
tilly's comment about things being "nearly linear" threw me for a bit. Then I realized that the quadratic nature is countered by the outer loop only needing to run to sqrt(N) and the inner loop being somewhat similarly restricted.
Which made me realize that my solution was suboptimal. Here is a faster one at the same number of characters [ thanks to MeowChow noting that I'd stupidly left in a trailing semicolon in my previous one ;) ]:
sub sieve3 { grep{@_[map$a*$_,$_..@_/($a=$_)]=0if$_[$_]>1}@_=0..pop } # ^^ for( @ARGV ) { print "$_: ",join(" ",sieve3($_)),$/; }
In playing with this and verifying that I didn't break it, I noticed something interesting and expanded on it. For how long of a stretch can you go without hitting any prime numbers? Well, stopping at 0.5million (because of memory limits), here are the results. "xN" means there were N ties before a new "winner" appeared:
- tye (but my friends call me "Tye")2=5-3(x2) # 3..5, 5..7 4=11-7(x3) # 7..11, 13..17, 19..23 6=29-23(x7) 8=97-89 14=127-113(x3) 18=541-523 20=907-887 22=1151-1129 34=1361-1327(x2) 36=9587-9551(x3) 44=15727-15683 52=19661-19609(x2) 72=31469-31397 86=156007-155921(x2) 96=360749-360653 112=370373-370261 114=492227-492113
|
---|
Replies are listed 'Best First'. | |
---|---|
Re (tilly) 4: (Golf): Sieve of Eratosthenes
by tilly (Archbishop) on May 21, 2001 at 20:37 UTC | |
Re: (tye)Re3: (Golf): Sieve of Eratosthenes
by tilly (Archbishop) on Feb 26, 2011 at 01:23 UTC |