1 ! Copyright (C) 2009 Samuel Tardieu.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: arrays byte-arrays kernel math math.bitwise math.functions math.order
4 math.ranges sequences sequences.private ;
10 { f 128 f f f f f 64 f f f 32 f 16 f f f 8 f 4 f f f 2 f f f f f 1 }
12 : bit-pos ( n -- byte mask/f )
13 30 /mod masks nth-unsafe ; inline
15 : marked-unsafe? ( n arr -- ? )
17 [ [ nth-unsafe ] [ bitand zero? not ] bi* ] [ 2drop f ] if* ; inline
21 pick [ [ swap unmask ] change-nth-unsafe ] [ 3drop ] if ; inline
23 : upper-bound ( arr -- n ) length 30 * 1 - ; inline
25 : unmark-multiples ( i arr -- )
27 [ [ dup sq ] [ upper-bound ] bi* rot <range> ] keep
33 : init-sieve ( n -- arr ) 30 /i 1 + 255 <array> >byte-array ; inline
38 init-sieve [ 2 swap upper-bound sqrt [a,b] ] keep
39 [ [ unmark-multiples ] curry each ] keep ;
41 : marked-prime? ( n arr -- ? )
42 2dup upper-bound 2 swap between? [ bounds-error ] unless
43 over { 2 3 5 } member? [ 2drop t ] [ marked-unsafe? ] if ;