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