extra/math/erato/erato.factor

   1 ! Copyright (c) 2007 Samuel Tardieu.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: bit-arrays kernel lazy-lists math math.functions math.primes.list
   4        math.ranges sequences ;
   5 IN: math.erato
   6
   7 <PRIVATE
   8
   9 TUPLE: erato limit bits latest ;
  10
  11 : ind ( n -- i )
  12   2/ 1- ; inline
  13
  14 : is-prime ( n erato -- bool )
  15   >r ind r> erato-bits nth ; inline
  16
  17 : indices ( n erato -- range )
  18   erato-limit ind over 3 * ind swap rot <range> ;
  19
  20 : mark-multiples ( n erato -- )
  21   over sq over erato-limit <=
  22   [ [ indices ] keep erato-bits [ f -rot set-nth ] curry each ] [ 2drop ] if ;
  23
  24 : <erato> ( n -- erato )
  25   dup ind 1+ <bit-array> 1 over set-bits erato boa ;
  26
  27 : next-prime ( erato -- prime/f )
  28   [ erato-latest 2 + ] keep [ set-erato-latest ] 2keep
  29   2dup erato-limit <=
  30   [
  31     2dup is-prime [ dupd mark-multiples ] [ nip next-prime ] if
  32   ] [
  33     2drop f
  34   ] if ;
  35
  36 PRIVATE>
  37
  38 : lerato ( n -- lazy-list )
  39   dup 1000003 < [
  40     0 primes-under-million seq>list swap [ <= ] curry lwhile
  41   ] [
  42     <erato> 2 [ drop next-prime ] with lfrom-by [ ] lwhile
  43   ] if ;