basis/math/primes/erato/erato.factor

   1 ! Copyright (C) 2009 Samuel Tardieu.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: bit-arrays kernel math math.functions math.ranges sequences ;
   4 IN: math.primes.erato
   5
   6 : >index ( n -- i )
   7     3 - 2 /i ; inline
   8
   9 : index> ( i -- n )
  10     2 * 3 + ; inline
  11
  12 : mark-multiples ( i arr -- )
  13     [ index> [ sq >index ] keep ] dip
  14     [ length 1 - swap <range> f swap ] keep
  15     [ set-nth ] curry with each ;
  16
  17 : maybe-mark-multiples ( i arr -- )
  18     2dup nth [ mark-multiples ] [ 2drop ] if ;
  19
  20 : init-sieve ( n -- arr )
  21     >index 1 + <bit-array> dup set-bits ;
  22
  23 : sieve ( n -- arr )
  24     [ init-sieve ] [ sqrt >index [0,b] ] bi
  25     over [ maybe-mark-multiples ] curry each ; foldable