1 ! Copyright (c) 2007 Samuel Tardieu.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: bit-arrays kernel lists lists.lazy math math.functions math.primes.list
4 math.ranges sequences ;
9 TUPLE: erato limit bits latest ;
14 : is-prime ( n erato -- bool )
15 >r ind r> erato-bits nth ; inline
17 : indices ( n erato -- range )
18 erato-limit ind over 3 * ind swap rot <range> ;
20 : mark-multiples ( n erato -- )
21 over sq over erato-limit <=
22 [ [ indices ] keep erato-bits [ f -rot set-nth ] curry each ] [ 2drop ] if ;
24 : <erato> ( n -- erato )
25 dup ind 1+ <bit-array> 1 over set-bits erato boa ;
27 : next-prime ( erato -- prime/f )
28 [ erato-latest 2 + ] keep [ set-erato-latest ] 2keep
31 2dup is-prime [ dupd mark-multiples ] [ nip next-prime ] if
38 : lerato ( n -- lazy-list )
40 0 primes-under-million seq>list swap [ <= ] curry lwhile
42 <erato> 2 [ drop next-prime ] with lfrom-by [ ] lwhile