extra/math/primes/primes.factor

   1 ! Copyright (C) 2007 Samuel Tardieu.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: combinators kernel lists.lazy math math.functions math.miller-rabin
   4        math.order math.primes.list math.ranges sequences sorting
   5        binary-search ;
   6 IN: math.primes
   7
   8 <PRIVATE
   9
  10 : find-prime-miller-rabin ( n -- p )
  11   dup miller-rabin [ 2 + find-prime-miller-rabin ] unless ; foldable
  12
  13 PRIVATE>
  14
  15 : next-prime ( n -- p )
  16   dup 999983 < [
  17     primes-under-million [ natural-search drop 1+ ] keep nth
  18   ] [
  19     next-odd find-prime-miller-rabin
  20   ] if ; foldable
  21
  22 : prime? ( n -- ? )
  23   dup 1000000 < [
  24     dup primes-under-million natural-search nip =
  25   ] [
  26     miller-rabin
  27   ] if ; foldable
  28
  29 : lprimes ( -- list )
  30   0 primes-under-million seq>list
  31   1000003 [ 2 + find-prime-miller-rabin ] lfrom-by
  32   lappend ;
  33
  34 : lprimes-from ( n -- list )
  35   dup 3 < [ drop lprimes ] [  1- next-prime [ next-prime ] lfrom-by ] if ;
  36
  37 : primes-upto ( n -- seq )
  38   {
  39     { [ dup 2 < ] [ drop { } ] }
  40     { [ dup 1000003 < ]
  41       [ primes-under-million [ natural-search drop 1+ 0 swap ] keep <slice> ] }
  42     [ primes-under-million 1000003 lprimes-from
  43         rot [ <= ] curry lwhile list>array append ]
  44   } cond ; foldable
  45
  46 : primes-between ( low high -- seq )
  47   primes-upto
  48   [ 1- next-prime ] dip
  49   [ natural-search drop ] keep [ length ] keep <slice> ; foldable
  50
  51 : coprime? ( a b -- ? ) gcd nip 1 = ; foldable